Problem Statement

Takahashi can combine a head part and a body part to create a robot. A robot falls over if the weight of the head part is greater than the weight of the body part.

Currently, he has one head part and one body part. The weight of the head part is H grams, and the weight of the body part is B grams.

He wants to make the body part heavier so that the robot does not fall over. Find how many more grams the body part needs to be made heavier so that his robot does not fall over.

Constraints

• 1\le H\le100
• 1\le B\le100
• All input values are integers.

Sample Input 1

43 1

Sample Output 1

42

By making the body part 42 grams heavier, Takahashi can make the weights of the head part and body part equal.

When the amount by which the body part is made heavier is less than 42 grams, his robot will fall over, so print 42.

Sample Input 2

4 31

Sample Output 2

0

Even if he creates the robot as is, the robot will not fall over, so print 0.

Sample Input 3

1 1

Sample Output 3

0

Problem Statement

You have a bankbook from The Terrifying Bank. The deposit passbook of the bank has a terrifyingly scary property that the commission fee changes according to the withdrawal amount.

To withdraw money from the passbook, you need to specify the withdrawal amount in units of 1\,000 yen, and pay a commission fee of C yen per 1\,000 yen of withdrawal amount separately from the balance. Withdrawals are not allowed if they would leave the balance below 0 yen.

When the balance of your passbook from the bank is X yen, what is the maximum amount of money you can withdraw from it?

Constraints

• 1 \leq X \leq 10^7
• 1 \leq C \leq 999
• All input values are integers.

Sample Input 1

650000 8

Sample Output 1

644000

The commission fee required to withdraw 644\,000 yen is 644\,000 \times \displaystyle\frac{8}{1000} = 5\,152 yen, so since 644\,000 + 5\,152 \leq 650\,000, you can withdraw 644\,000 yen.

On the other hand, the commission fee required to withdraw 645\,000 yen is 645\,000 \times \displaystyle\frac{8}{1000} = 5\,160 yen, so since 645\,000 + 5\,160 > 650\,000, you cannot withdraw 645\,000 yen.

Sample Input 2

1003 4

Sample Output 2

0

It is possible that no money can be withdrawn at all.

Sample Input 3

10000000 24

Sample Output 3

9765000

Problem Statement

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

• A_i is 0 or 1.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

13

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

Problem Statement

Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.

The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.

Takahashi has decided to call a time a confusing time if it satisfies the following condition:

• after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.

For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.

The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.

Constraints

• 0 \leq H \leq 23
• 0 \leq M \leq 59
• H and M are integers.

Sample Input 1

1 23

Sample Output 1

1 23

1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.

Sample Input 2

19 57

Sample Output 2

20 0

The next confusing time after 19:57 is 20:00.

Sample Input 3

20 40

Sample Output 3

21 0

Note that 24:00 is an invalid notation in the 24-hour system.

Problem Statement

The definition of an 11/22 string in this problem is the same as in Problems A and E.

A string T is called an 11/22 string when it satisfies all of the following conditions:

• |T| is odd. Here, |T| denotes the length of T.
• The 1-st through (\frac{|T|+1}{2} - 1)-th characters are all 1.
• The (\frac{|T|+1}{2})-th character is /.
• The (\frac{|T|+1}{2} + 1)-th through |T|-th characters are all 2.

For example, 11/22, 111/222, and / are 11/22 strings, but 1122, 1/22, 11/2222, 22/11, and //2/2/211 are not.

You are given a string S of length N consisting of 1, 2, and /, where S contains at least one /.
Find the maximum length of a (contiguous) substring of S that is an 11/22 string.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 1, 2, and /.
• S contains at least one /.

Sample Input 1

8
211/2212

Sample Output 1

5

The substring from the 2-nd to 6-th character of S is 11/22, which is an 11/22 string. Among all substrings of S that are 11/22 strings, this is the longest. Therefore, the answer is 5.

Sample Input 2

5
22/11

Sample Output 2

1

Sample Input 3

22
/1211/2///2111/2222/11

Sample Output 3

7

Problem Statement

Takahashi is standing at the coordinate 0 on a number line.

He will now perform N jumps. In the i-th jump (1 \leq i \leq N), he moves a_i or b_i in the positive direction.

Is it possible for him to be at the coordinate X after N jumps?

Constraints

• 1 \leq N \leq 100
• 1 \leq a_i \lt b_i \leq 100 \, (1 \leq i \leq N)
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

2 10
3 6
4 5

Sample Output 1

Yes

By moving b_1 (= 6) in the first jump and a_2 (= 4) in the second jump, he can be at the coordinate X (= 10).

Sample Input 2

2 10
10 100
10 100

Sample Output 2

No

He can be at the coordinate X (= 10) after the first jump, but not after all jumps.

Sample Input 3

4 12
1 8
5 7
3 4
2 6

Sample Output 3

Yes

Problem Statement

You are given two sequences of positive integers of length N, L=(L_1,L_2,\ldots,L_N) and R=(R_1,R_2,\ldots,R_N), and an integer M.

Find the number of pairs of integers (l,r) that satisfy both of the following conditions:

• 1\le l \le r \le M
• For every 1\le i\le N, the interval [l,r] does not completely contain the interval [L_i,R_i].

Constraints

• 1\le N,M\le 2\times 10^5
• 1\le L_i\le R_i\le M
• All input values are integers.

Sample Input 1

2 4
1 2
3 4

Sample Output 1

5

The five pairs (l,r)=(1,1),(2,2),(2,3),(3,3),(4,4) satisfy the conditions.

For example, (l,r)=(1,3) does not satisfy the conditions because the interval [1,3] completely contains the interval [1,2].

Sample Input 2

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

Sample Output 2

0

There may be cases where no pairs of integers satisfy the conditions.

Sample Input 3

6 20
8 12
14 20
11 13
5 19
4 11
1 6

Sample Output 3

102

Problem Statement

There are N people divided into three teams.

The people are numbered 1, 2, \ldots, N, and the teams are numbered 1, 2, 3. Currently, person i belongs to team A_i.

Each person has a value called strength; person i has a strength of B_i. The strength of a team is defined as the sum of the strengths of its members.

Determine whether it is possible for zero or more people to switch teams so that all teams have equal strength. If it is possible, find the minimum number of people who need to switch teams to achieve this.

You cannot create new teams other than teams 1, 2, 3.

Constraints

• 3 \leq N \leq 100
• A_i \in \lbrace 1, 2, 3 \rbrace
• For each x \in \lbrace 1, 2, 3 \rbrace, there exists some i with A_i = x.
• 1 \leq B_i
• \displaystyle\sum_{i = 1}^{N} B_i \leq 1500
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

If person 1 switches to team 3 and person 4 switches to team 2, all teams will have a strength of 8.

Sample Input 2

4
1 1
1 2
2 3
3 4

Sample Output 2

-1

Sample Input 3

3
1 1
2 1
3 1

Sample Output 3

0

Sample Input 4

12
2 5
1 4
3 3
2 3
3 9
1 2
2 2
3 9
2 6
1 9
1 1
3 1

Sample Output 4

3

Problem Statement

There are N cat towers arranged in a row from left to right, and the height of the i-th tower from the left (1\leq i\leq N) is P_i.
Here, (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
The distance between the i-th tower and the j-th tower from the left is defined as \lvert i-j\rvert.

There is one cat, initially on top of the cat tower of height N.
Takahashi wants to exercise this cat by repeatedly choosing and removing towers.

When Takahashi removes a tower, the cat moves as follows:

• If the cat is not on top of the tower being removed, the cat does not move.
• If the cat is on top of the tower being removed and at least one of the towers adjacent to the left or right of that tower exists, the cat moves to the tallest tower (excluding the tower being removed) among the towers that can be reached by repeatedly moving to adjacent towers starting from the tower being removed. At this time, the cat moves the distance between the tower before movement and the tower after movement (the heights of the towers before, after, and during movement do not matter).
• If the cat is on top of the tower being removed and no towers adjacent to the left or right of that tower exist, the cat jumps into Takahashi's arms, and the exercise ends here. In this case, no movement occurs.

Here, the spaces between removed towers are not filled in. That is, the towers adjacent to the i-th tower from the left initially are only the (i-1)-th and (i+1)-th towers from the left (if they exist), and they will never become adjacent to other towers due to the removal of other towers afterward.

Find the maximum possible total distance the cat moves before the exercise ends.

Constraints

• 1\leq N\leq 2\times 10^5
• (P_1,P_2,\ldots, P_N) is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5
5 3 4 1 2

Sample Output 1

5

Initially, the heights of the cat towers are 5,3,4,1,2 from left to right.
Hereafter, the i-th cat tower from the left (1\leq i\leq 5) is called tower i.
Initially, the cat is on tower 1 (height 5).

If Takahashi removes towers in the order 1,2,3,5,4, the cat moves as follows:

• Takahashi removes tower 1. The towers that can be reached by only moving to adjacent towers from tower 1 are towers 2,3,4,5 (excluding tower 1). The cat moves to tower 3 (height 4), which is the tallest among them.
• Takahashi removes tower 2. The cat does not move.
• Takahashi removes tower 3. The towers that can be reached by only moving to adjacent towers from tower 3 are towers 4,5 (excluding tower 3). The cat moves to tower 5 (height 2), which is the tallest among them.
• Takahashi removes tower 5. The towers that can be reached by only moving to adjacent towers from tower 5 are only tower 4 (excluding tower 5). The cat moves to tower 4 (height 1).
• Takahashi removes tower 4. The cat jumps into Takahashi's arms, and the exercise ends.

Here, the cat moves the total distance of \lvert 1-3\rvert+\lvert 3-5\rvert+\lvert 5-4\rvert=5. There is no way to remove towers that makes the total distance moved 6 or more, so output 5.

Sample Input 2

3
1 3 2

Sample Output 2

1

Initially, the heights of the cat towers are 1,3,2 from left to right.
Hereafter, the i-th cat tower from the left (1\leq i\leq 3) is called tower i.
Initially, the cat is on tower 2 (height 3).

If Takahashi removes towers in the order 2,3, the cat moves as follows:

• Takahashi removes tower 2. The towers that can be reached by only moving to adjacent towers from tower 2 are towers 1,3 (excluding tower 2). The cat moves to tower 3 (height 2), which is the tallest among them.
• Takahashi removes tower 3. The cat jumps into Takahashi's arms, and the exercise ends.

Here, the cat moves the total distance of \lvert 2-3\rvert=1, which is the maximum.
Note that after removing tower 2, tower 1 and tower 3 are not considered to be adjacent.