Problem Statement

We have A apples and P pieces of apple.

We can cut an apple into three pieces of apple, and make one apple pie by simmering two pieces of apple in a pan.

Find the maximum number of apple pies we can make with what we have now.

Constraints

• All values in input are integers.
• 0 \leq A, P \leq 100

Sample Input 1

1 3

Sample Output 1

3

We can first make one apple pie by simmering two of the three pieces of apple. Then, we can make two more by simmering the remaining piece and three more pieces obtained by cutting the whole apple.

Sample Input 2

0 1

Sample Output 2

0

We cannot make an apple pie in this case, unfortunately.

Sample Input 3

32 21

Sample Output 3

58

Problem Statement

You have decided to write a book introducing good restaurants. There are N restaurants that you want to introduce: Restaurant 1, Restaurant 2, ..., Restaurant N. Restaurant i is in city S_i, and your assessment score of that restaurant on a 100-point scale is P_i. No two restaurants have the same score.

You want to introduce the restaurants in the following order:

• The restaurants are arranged in lexicographical order of the names of their cities.
• If there are multiple restaurants in the same city, they are arranged in descending order of score.

Print the identification numbers of the restaurants in the order they are introduced in the book.

Constraints

• 1 ≤ N ≤ 100
• S is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• 0 ≤ P_i ≤ 100
• P_i is an integer.
• P_i ≠ P_j (1 ≤ i < j ≤ N)

Sample Input 1

6
khabarovsk 20
moscow 10
kazan 50
kazan 35
moscow 60
khabarovsk 40

Sample Output 1

3
4
6
1
5
2

The lexicographical order of the names of the three cities is kazan < khabarovsk < moscow. For each of these cities, the restaurants in it are introduced in descending order of score. Thus, the restaurants are introduced in the order 3,4,6,1,5,2.

Sample Input 2

10
yakutsk 10
yakutsk 20
yakutsk 30
yakutsk 40
yakutsk 50
yakutsk 60
yakutsk 70
yakutsk 80
yakutsk 90
yakutsk 100

Sample Output 2

10
9
8
7
6
5
4
3
2
1

Problem Statement

We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N, and the bulbs are numbered 1 to M.

Bulb i is connected to k_i switches: Switch s_{i1}, s_{i2}, ..., and s_{ik_i}. It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

• 1 \leq N, M \leq 10
• 1 \leq k_i \leq N
• 1 \leq s_{ij} \leq N
• s_{ia} \neq s_{ib} (a \neq b)
• p_i is 0 or 1.
• All values in input are integers.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

• Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.
• Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

There are four possible combinations of states of (Switch 1, Switch 2): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1.

Sample Input 2

2 3
2 1 2
1 1
1 2
0 0 1

Sample Output 2

0

• Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.
• Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1.
• Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3, but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8

Problem Statement

Your friend gave you a dequeue D as a birthday present.

D is a horizontal cylinder that contains a row of N jewels.

The values of the jewels are V_1, V_2, ..., V_N from left to right. There may be jewels with negative values.

In the beginning, you have no jewel in your hands.

You can perform at most K operations on D, chosen from the following, at most K times (possibly zero):

• Operation A: Take out the leftmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.

• Operation B: Take out the rightmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.

• Operation C: Choose a jewel in your hands and insert it to the left end of D. You cannot do this operation when you have no jewel in your hand.

• Operation D: Choose a jewel in your hands and insert it to the right end of D. You cannot do this operation when you have no jewel in your hand.

Find the maximum possible sum of the values of jewels in your hands after the operations.

Constraints

• All values in input are integers.
• 1 \leq N \leq 50
• 1 \leq K \leq 100
• -10^7 \leq V_i \leq 10^7

Sample Input 1

6 4
-10 8 2 1 2 6

Sample Output 1

14

After the following sequence of operations, you have two jewels of values 8 and 6 in your hands for a total of 14, which is the maximum result.

• Do operation A. You take out the jewel of value -10 from the left end of D.
• Do operation B. You take out the jewel of value 6 from the right end of D.
• Do operation A. You take out the jewel of value 8 from the left end of D.
• Do operation D. You insert the jewel of value -10 to the right end of D.

Sample Input 2

6 4
-6 -100 50 -2 -5 -3

Sample Output 2

44

Sample Input 3

6 3
-6 -100 50 -2 -5 -3

Sample Output 3

0

It is optimal to do no operation.

Problem Statement

There is an infinitely long street that runs west to east, which we consider as a number line.

There are N roadworks scheduled on this street. The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.

Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the Q people will walk.

Constraints

• All values in input are integers.
• 1 \leq N, Q \leq 2 \times 10^5
• 0 \leq S_i < T_i \leq 10^9
• 1 \leq X_i \leq 10^9
• 0 \leq D_1 < D_2 < ... < D_Q \leq 10^9
• If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Sample Input 1

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

Sample Output 1

2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.

The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.

The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.

Problem Statement

There is an infinitely large pond, which we consider as a number line. In this pond, there are N lotuses floating at coordinates 0, 1, 2, ..., N-2 and N-1. On the lotus at coordinate i, an integer s_i is written.

You are standing on the lotus at coordinate 0. You will play a game that proceeds as follows:

• 1. Choose positive integers A and B. Your score is initially 0.
• 2. Let x be your current coordinate, and y = x+A. The lotus at coordinate x disappears, and you move to coordinate y.
  • If y = N-1, the game ends.
  • If y \neq N-1 and there is a lotus floating at coordinate y, your score increases by s_y.
  • If y \neq N-1 and there is no lotus floating at coordinate y, you drown. Your score decreases by 10^{100} points, and the game ends.
• 3. Let x be your current coordinate, and y = x-B. The lotus at coordinate x disappears, and you move to coordinate y.
  • If y = N-1, the game ends.
  • If y \neq N-1 and there is a lotus floating at coordinate y, your score increases by s_y.
  • If y \neq N-1 and there is no lotus floating at coordinate y, you drown. Your score decreases by 10^{100} points, and the game ends.
• 4. Go back to step 2.

You want to end the game with as high a score as possible. What is the score obtained by the optimal choice of A and B?

Constraints

• 3 \leq N \leq 10^5
• -10^9 \leq s_i \leq 10^9
• s_0=s_{N-1}=0
• All values in input are integers.

Sample Input 1

5
0 2 5 1 0

Sample Output 1

3

If you choose A = 3 and B = 2, the game proceeds as follows:

• Move to coordinate 0 + 3 = 3. Your score increases by s_3 = 1.
• Move to coordinate 3 - 2 = 1. Your score increases by s_1 = 2.
• Move to coordinate 1 + 3 = 4. The game ends with a score of 3.

There is no way to end the game with a score of 4 or higher, so the answer is 3. Note that you cannot land the lotus at coordinate 2 without drowning later.

Sample Input 2

6
0 10 -7 -4 -13 0

Sample Output 2

0

The optimal strategy here is to land the final lotus immediately by choosing A = 5 (the value of B does not matter).

Sample Input 3

11
0 -4 0 -99 31 14 -15 -39 43 18 0

Sample Output 3

59