Problem Statement

Team Takahashi and Team Aoki played N matches. In the i-th match (1\leq i\leq N), Team Takahashi scored X _ i points, and Team Aoki scored Y _ i points.

The team with the higher total score from the N matches wins.

Print the winner. If the two teams have the same total score, it is a draw.

Constraints

• 1\leq N\leq 100
• 0\leq X _ i\leq 100\ (1\leq i\leq N)
• 0\leq Y _ i\leq 100\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

4
10 2
10 1
10 2
3 2

Sample Output 1

Takahashi

In four matches, Team Takahashi scored 33 points, and Team Aoki scored 7 points. Team Takahashi wins, so print Takahashi.

Sample Input 2

6
5 4
4 5
2 4
1 6
7 1
3 2

Sample Output 2

Draw

Both teams scored 22 points. It is a draw, so print Draw.

Sample Input 3

4
0 0
10 10
50 50
0 100

Sample Output 3

Aoki

One or both teams may score no points in a match.

Problem Statement

You are given a string S consisting of lowercase English letters.
If a appears in S, print the last index at which it appears; otherwise, print -1. (The index starts at 1.)

Constraints

• S is a string of length between 1 and 100 (inclusive) consisting of lowercase English letters.

Sample Input 1

abcdaxayz

Sample Output 1

7

a appears three times in S. The last occurrence is at index 7, so you should print 7.

Sample Input 2

bcbbbz

Sample Output 2

-1

a does not appear in S, so you should print -1.

Sample Input 3

aaaaa

Sample Output 3

5

Problem Statement

There is a grid of 64 squares with 8 rows and 8 columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq8) and j-th column from the left (1\leq j\leq8).

Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence (S_1,S_2,S_3,\ldots,S_8) of 8 strings of length 8. Square (i,j) (1\leq i\leq8,1\leq j\leq8) is empty if the j-th character of S_i is ., and has a piece if it is #.

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy either of the following conditions:

• Placed on a square in row i
• Placed on a square in column j

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

• Each S_i is a string of length 8 consisting of . and # (1\leq i\leq 8).

Sample Input 1

...#....
#.......
.......#
....#...
.#......
........
........
..#.....

Sample Output 1

4

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece without it being captured on 4 squares: square (6,6), square (6,7), square (7,6), and square (7,7).

Sample Input 2

........
........
........
........
........
........
........
........

Sample Output 2

64

There may be no pieces on the grid.

Sample Input 3

.#......
..#..#..
....#...
........
..#....#
........
...#....
....#...

Sample Output 3

4

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

• 1 \leq N \leq 2000
• 0 \leq A_i \leq 2000
• All values in input are integers.

Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.

Sample Input 2

3
2000 2000 2000

Sample Output 2

0

Problem Statement

A region has N towns numbered 1 to N, and M roads numbered 1 to M.

The i-th road connects town A_i and town B_i bidirectionally with length C_i.

Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• The pairs (A_i,B_i) are distinct.
• 1\leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

Sample Output 1

1110

If you travel as 4\to 1\to 3\to 2, the total length of the roads you traverse is 1110.

Sample Input 2

10 1
5 9 1

Sample Output 2

1

There may be a town that is not connected to a road.

Sample Input 3

10 13
1 2 1
1 10 1
2 3 1
3 4 4
4 7 2
4 8 1
5 8 1
5 9 3
6 8 1
6 9 5
7 8 1
7 9 4
9 10 3

Sample Output 3

20

Problem Statement

There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.

Find how many different kinds of kagamimochi can be made.

Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• A_i \leq A_{i+1} \ (1 \leq i < N)
• All input values are integers.

Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

8

The sizes of the given mochi are as follows:

In this case, you can make the following eight kinds of kagamimochi:

Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.

Sample Input 2

3
387 388 389

Sample Output 2

0

It is possible that you cannot make any kagamimochi.

Sample Input 3

32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641

Sample Output 3

388

Problem Statement

A function f(x) defined for non-negative integers x satisfies the following conditions.

• f(0) = 1.
• f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) for any positive integer k.

Here, \lfloor A \rfloor denotes the value of A rounded down to an integer.

Find f(N).

Constraints

• N is an integer satisfying 0 \le N \le 10^{18}.

Sample Input 1

2

Sample Output 1

3

We have f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3.

Sample Input 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55

Problem Statement

There are N types of products, each having 10^{100} units in stock.

You can buy any non-negative number of units of each product. To buy k units of the i-th product, it costs k^2 P_i yen.

If your total purchase cost is at most M yen, what is the maximum number of units you can buy in total?

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq M \leq 10^{18}
• 1 \leq P_i \leq 2 \times 10^{9}
• All input values are integers.

Sample Input 1

3 9
4 1 9

Sample Output 1

3

If you buy one unit of the 1st product and two units of the 2nd product, the total purchase cost is 1^2 \times 4 + 2^2 \times 1 = 8. It is impossible to buy four or more units in total with a total cost of at most 9 yen, so the answer is 3.

Sample Input 2

10 1000
2 15 6 5 12 1 7 9 17 2

Sample Output 2

53

Problem Statement

There are N types of items. The i-th type of item has a weight of w_i and a value of v_i. Each type has 10^{10} items available.

Takahashi is going to choose some items and put them into a bag with capacity W. He wants to maximize the value of the selected items while avoiding choosing too many items of the same type. Hence, he defines the happiness of choosing k_i items of type i as k_i v_i - k_i^2. He wants to choose items to maximize the total happiness over all types while keeping the total weight at most W. Calculate the maximum total happiness he can achieve.

Constraints

• 1 \leq N \leq 3000
• 1 \leq W \leq 3000
• 1 \leq w_i \leq W
• 1 \leq v_i \leq 10^9
• All input values are integers.

Sample Input 1

2 10
3 4
3 2

Sample Output 1

5

By choosing 2 items of type 1 and 1 item of type 2, the total happiness can be 5, which is optimal.

Here, the happiness for type 1 is 2 \times 4 - 2^2 = 4, and the happiness for type 2 is 1 \times 2 - 1^2 = 1.

The total weight is 9, which is within the capacity 10.

Sample Input 2

3 6
1 4
2 3
2 7

Sample Output 2

14

Sample Input 3

1 10
1 7

Sample Output 3

12