Problem Statement

Given a string S, print AC if it perfectly matches Hello,World!; otherwise, print WA.

Constraints

• 1 \le |S| \le 15
• S consists of English lowercase letters, English uppercase letters, ,, and !.

Sample Input 1

Hello,World!

Sample Output 1

AC

The string S perfectly matches Hello,World!.

Sample Input 2

Hello,world!

Sample Output 2

WA

The seventh character from the beginning should be an uppercase W in Hello,World!, but S has a lowercase w in that position. Thus, S does not match Hello,World!.

Sample Input 3

Hello!World!

Sample Output 3

WA

Problem Statement

Takahashi is playing a game. This game has eight worlds, and each world has eight stages. The stages have an order, and the first stage is the 1st stage in the 1st world. The next stage after the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is as follows:

• When j\lt8, the next stage is the (j+1)-th stage in the i-th world.
• When i\lt8,j=8, the next stage is the 1st stage in the (i+1)-th world.
• When i=8,j=8, there is no next stage. This stage is the last stage.

The name of the j-th stage (1\le j\le 8) in the i-th world (1\le i\le 8) is i-j. For example, the name of the first stage is 1-1, and the name of the last stage is 8-8.

Given the stage name S of the stage Takahashi is currently playing, output the stage name of the next stage.

Constraints

• S is the stage name of one of the stages.
• S is not 8-8.

Sample Input 1

4-2

Sample Output 1

4-3

The next stage after the 2nd stage in the 4th world is the 3rd stage in the same world.

Sample Input 2

1-8

Sample Output 2

2-1

1-8 is the last stage in the 1st world, so the next stage is the 1st stage in the 2nd world.

Sample Input 3

3-3

Sample Output 3

3-4

Problem Statement

There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:

• We can choose at most 3 different weights so that they have a total mass of n.

How many positive integers less than or equal to W are good integers?

Constraints

• 1 \leq N \leq 300
• 1 \leq W \leq 10^6
• 1 \leq A_i \leq 10^6
• All values in input are integers.

Sample Input 1

2 10
1 3

Sample Output 1

3

If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.

Sample Input 2

2 1
2 3

Sample Output 2

0

There are no good integers less than or equal to W.

Sample Input 3

4 12
3 3 3 3

Sample Output 3

3

There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.

Sample Input 4

7 251
202 20 5 1 4 2 100

Sample Output 4

48

Problem Statement

There is pasta consisting of N noodles at Takahashi's home. The length of the i-th noodle is A_i.
Takahashi has a meal plan for the next M days. On the i-th day, he is going to choose a pasta noodle of length exactly B_i and eat it. If no such noodle is available on any day, his plan fails. Additionally, he cannot eat the same noodle on multiple days.

Can Takahashi accomplish his meal plan?

Constraints

• 1 \leq M \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

3 2
1 1 3
3 1

Sample Output 1

Yes

He can eat the 3-rd noodle on the 1-st day and the 1-st noodle on the 2-nd day, so his meal plan is feasible.

Sample Input 2

1 1
1000000000
1

Sample Output 2

No

A noodle of length exactly 1 is needed.

Sample Input 3

5 2
1 2 3 4 5
5 5

Sample Output 3

No

Since there are only 1 noodle of length 5, he cannot have a meal on the 2-nd day.

Problem Statement

Takahashi is a cashier.

There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The cash register initially displays 0. Whenever he types the key 00, the displayed number is multiplied by 100; whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.

Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?

Constraints

• 1\leq S\leq 10^{100000}
• S is an integer.

Sample Input 1

40004

Sample Output 1

4

For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.

• Type the key 4. It now displays 4.
• Type the key 00. It now displays 400.
• Type the key 0. It now displays 4000.
• Type the key 4. It now displays 40004.

He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.

Sample Input 2

1355506027

Sample Output 2

10

Sample Input 3

10888869450418352160768000001

Sample Output 3

27

Note that S may not fit into a 64-\operatorname{bit} integer type.

Problem Statement

There are N cells numbered from 1 to N in a row. Initially, M cells contain stones, and cell X_i contains A_i stones (1 \leq i \leq M).

You can perform the following operation any number of times (possibly zero):

• If cell i (1 \leq i \leq N-1) contains a stone, move one stone from cell i to cell i+1.

Find the minimum number of operations required to reach a state where each of the N cells contains exactly one stone. If it is impossible, print -1.

Constraints

• 2 \leq N \leq 2 \times 10^{9}
• 1 \leq M \leq 2 \times 10^{5}
• M \leq N
• 1 \leq X_i \leq N (1 \leq i \leq M)
• X_i \neq X_j (1 \leq i < j \leq M)
• 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

5 2
1 4
3 2

Sample Output 1

4

You can reach a state where each of the five cells contains exactly one stone with four operations as follows:

• Move one stone from cell 1 to cell 2.
• Move one stone from cell 2 to cell 3.
• Move one stone from cell 4 to cell 5.
• Move one stone from cell 1 to cell 2.

It is impossible to achieve the goal in three or fewer operations. Therefore, print 4.

Sample Input 2

10 3
1 4 8
4 2 4

Sample Output 2

-1

No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print -1.

Problem Statement

You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.
The states of the cells are given by N strings of length N, S_1, S_2, \dots, S_N, in the following format:

• If the j-th character of S_i is o, there is an o written in cell (i,j).
• If the j-th character of S_i is x, there is an x written in cell (i,j).

Find the number of triples of cells that satisfy all of the following conditions:

• The three cells in the triple are distinct.
• All three cells have an o written in them.
• Exactly two of the cells are in the same row.
• Exactly two of the cells are in the same column.

Here, two triples are considered different if and only if some cell is contained in exactly one of the triples.

Constraints

• N is an integer between 2 and 2000, inclusive.
• S_i is a string of length N consisting of o and x.

Sample Input 1

3
ooo
oxx
xxo

Sample Output 1

4

The following four triples satisfy the conditions:

• (1,1),(1,2),(2,1)
• (1,1),(1,3),(2,1)
• (1,1),(1,3),(3,3)
• (1,2),(1,3),(3,3)

Sample Input 2

4
oxxx
xoxx
xxox
xxxo

Sample Output 2

0

Sample Input 3

15
xooxxooooxxxoox
oxxoxoxxxoxoxxo
oxxoxoxxxoxoxxx
ooooxooooxxoxxx
oxxoxoxxxoxoxxx
oxxoxoxxxoxoxxo
oxxoxooooxxxoox
xxxxxxxxxxxxxxx
xooxxxooxxxooox
oxxoxoxxoxoxxxo
xxxoxxxxoxoxxoo
xooxxxooxxoxoxo
xxxoxxxxoxooxxo
oxxoxoxxoxoxxxo
xooxxxooxxxooox

Sample Output 3

2960

Problem Statement

The manufacturing of a certain product requires N processes numbered 1,2,\dots,N.

For each process i, there are two types of machines S_i and T_i available for purchase to handle it.

• Machine S_i: Can process A_i products per day per unit, and costs P_i yen per unit.
• Machine T_i: Can process B_i products per day per unit, and costs Q_i yen per unit.

You can purchase any number of each machine, possibly zero.

Suppose that process i can handle W_i products per day as a result of introducing machines.
Here, we define the production capacity as the minimum of W, that is, \displaystyle \min^{N}_{i=1} W_i.

Given a total budget of X yen, find the maximum achievable production capacity.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i,B_i \le 100
• 1 \le P_i,Q_i,X \le 10^7

Sample Input 1

3 22
2 5 3 6
1 1 3 3
1 3 2 4

Sample Output 1

4

For example, by introducing machines as follows, we can achieve a production capacity of 4, which is the maximum possible.

• For process 1, introduce 2 units of machine S_1.
  • This allows processing 4 products per day and costs a total of 10 yen.
• For process 2, introduce 1 unit of machine S_2.
  • This allows processing 1 product per day and costs a total of 1 yen.
• For process 2, introduce 1 unit of machine T_2.
  • This allows processing 3 products per day and costs a total of 3 yen.
• For process 3, introduce 2 units of machine T_3.
  • This allows processing 4 products per day and costs a total of 8 yen.

Sample Input 2

1 10000000
100 1 100 1

Sample Output 2

1000000000

Sample Input 3

1 1
1 10000000 1 10000000

Sample Output 3

0

There may be cases where a positive production capacity cannot be achieved.

Sample Input 4

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

Sample Output 4

894742

Problem Statement

There are N boxes numbered 1, 2, \ldots, N. Initially, box i contains one ball of color C_i.

You are given Q queries, which you should process in order.

Each query is given by a pair of integers (a,b) and asks you to do the following:

• Move all the balls from box a to box b, and then print the number of different colors of balls in box b.

Here, the boxes a and b may be empty.

Constraints

• 1 \leq N, Q \leq 200000
• 1 \leq C_i \leq N
• 1 \leq a, b \leq N
• a \neq b
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
2
1
1
3

• For the first query, move all the balls from box 1 to box 2. Box 2 now contains two balls of color 1, so print 1.

• For the second query, move all the balls from box 6 to box 4. Box 4 now contains one ball of color 2 and one ball of color 3, so print 2.

• For the third query, move all the balls from box 5 to box 1. Box 1 now contains one ball of color 2, so print 1.

• For the fourth query, move all the balls from box 3 to box 6. Box 6 now contains one ball of color 1, so print 1.

• For the fifth query, move all the balls from box 4 to box 6. Box 6 now contains one ball of color 1, one ball of color 2, and one ball of color 3, so print 3.

Sample Input 2

5 3
2 4 2 4 2
3 1
2 5
3 2

Sample Output 2

1
2
0