Problem Statement

Takahashi is growing N plants.

Currently, the height of the i-th plant is A_i millimeters. Each plant grows by a fixed length per day, and the i-th plant grows by B_i millimeters per day.

Find the total height of all N plants, in millimeters, after D days from now.

It is guaranteed that the answer does not exceed 2 \times 10^{16}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq D \leq 10^6
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_i \leq 10^5 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 5
10 2
20 3
15 1

Sample Output 1

75

Sample Input 2

2 1
100 100
1 1

Sample Output 2

202

Sample Input 3

8 30
5 2
12 4
7 1
20 3
100 10
50 5
33 7
18 2

Sample Output 3

1265

Sample Input 4

20 365
1000 12
850 7
920 9
1100 15
760 6
1340 11
980 8
1230 10
670 5
890 7
1450 13
710 4
1600 14
540 3
1180 9
1300 12
1020 6
970 8
880 5
1500 16

Sample Output 4

86590

Sample Input 5

1 1000000
1000000000 100000

Sample Output 5

101000000000

Problem Statement

Takahashi is hiking in a mountainous area and wants to enjoy the scenery from N observation decks arranged in a straight line at equal intervals. The observation decks are numbered 1, 2, \ldots, N from left to right, and the distance between observation deck i and observation deck j is |i - j|.

At each observation deck i, there stands a mountain of height H_i. When Takahashi stands at an observation deck and looks around to the left and right, mountains at other observation deck locations obstruct his view, changing the amount of visible sky.

Specifically, when Takahashi stands at observation deck p, the "sky openness" is defined as follows. Takahashi's eye level is 0. Note that the mountain at observation deck p itself does not obstruct Takahashi's view.

• Left obstruction degree: When looking left from observation deck p, the degree to which the mountain at observation deck l (l < p) obstructs the view is represented by the ratio of height to distance \frac{H_l}{p - l}. The left obstruction degree is defined as

L_p = \max_{1 \le l < p} \frac{H_l}{p - l}

However, when p = 1, there are no observation decks to the left, so L_p = 0.

• Right obstruction degree: Similarly, the right obstruction degree is defined as

R_p = \max_{p < r \le N} \frac{H_r}{r - p}

However, when p = N, there are no observation decks to the right, so R_p = 0.

• Sky openness: The sky openness at observation deck p is

V_p = \frac{1}{1 + L_p + R_p}

However, in the mountainous area, mountain heights occasionally change due to construction or natural phenomena.

Q events occur in order. Each event is one of the following two types:

• Type 1: The height of the mountain at observation deck x changes to h (i.e., the value of H_x is updated to h).
• Type 2: Among the observation decks in the range from observation deck a to observation deck b (a \le b), find the observation deck number with the maximum "sky openness" V_p at that point in time. If there are multiple observation decks with the maximum value, output the one with the smallest number.

Note that comparisons of V_p are performed based on exact values (rational numbers).

For each Type 2 event, find the answer.

Constraints

• 1 \leq N \leq 200
• 1 \leq Q \leq 200
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• For Type 1 events, 1 \leq x \leq N and 1 \leq h \leq 10^9
• For Type 2 events, 1 \leq a \leq b \leq N
• There is at least one Type 2 event
• All input values are integers

Sample Input 1

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

Sample Output 1

1
3
5

Sample Input 2

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

Sample Output 2

1
2
2

Sample Input 3

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

Sample Output 3

1
3
5
5
1
10

Sample Input 4

20 15
12 5 18 3 25 7 14 9 30 2 11 6 22 8 17 4 28 1 19 10
2 1 20
2 5 15
1 9 1
2 1 20
1 1 1000000000
2 1 5
2 18 20
1 17 1
2 10 20
2 1 20
1 5 1
1 15 500
2 1 20
2 7 13
2 19 20

Sample Output 4

1
9
1
1
20
20
1
1
13
20

Sample Input 5

1 1
1000000000
2 1 1

Sample Output 5

1

Problem Statement

Takahashi is an engineer at a telecommunications company. He has been assigned a project to lay new fiber optic cables.

There are N relay stations along a road, and each station is aligned in a straight line. The stations are numbered 1, 2, \ldots, N in order of increasing distance from the starting point of the road, and the i-th station is located X_i meters from the starting point (X_1 < X_2 < \cdots < X_N). Activating each station i costs C_i ten-thousand yen.

Takahashi's project has been allocated a budget of M ten-thousand yen. To lay the fiber optic cable, Takahashi can select one contiguous interval of stations. Specifically, he chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and activates all stations from the l-th to the r-th. The required cost is the total activation cost of all stations in the chosen interval, \displaystyle\sum_{i=l}^{r} C_i ten-thousand yen, which must not exceed the budget of M ten-thousand yen. Note that the cost of laying cables between stations can be ignored.

When a valid (l, r) is chosen under this condition, a fiber optic cable of X_r - X_l meters can be laid (if l = r, the length is 0 meters). If there is no interval that fits within the budget, or if Takahashi chooses not to select any interval, nothing is laid, and the cable length is 0 meters.

Find the maximum length of fiber optic cable that Takahashi can lay, in meters.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^{14}
• 1 \leq X_i \leq 10^9 (1 \leq i \leq N)
• X_1 < X_2 < \cdots < X_N
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 10
1 2
3 3
7 4
12 5
20 6

Sample Output 1

6

Sample Input 2

4 5
10 3
20 3
30 3
40 3

Sample Output 2

0

Sample Input 3

8 100
5 10
15 20
30 15
50 25
80 30
120 10
200 40
300 50

Sample Output 3

180

Problem Statement

Takahashi is trapped in a rectangular ice rink with H rows and W columns. There are N pillars standing inside the rink. The i-th pillar is located at coordinates (R_i, C_i). Here, coordinates (r, c) denote the cell in the r-th row from the top and the c-th column from the left.

Takahashi is currently at the top-left corner at coordinates (1, 1) and aims to reach the goal at the bottom-right corner at coordinates (H, W).

The ice on the rink is extremely slippery, and once he starts sliding, he cannot change direction or stop midway. In one move, Takahashi chooses one of the four directions — up, down, left, or right — and begins sliding, continuing straight in that direction until one of the following conditions is met:

• Reaching the edge of the rink: Since he cannot go outside the rink, he stops at the edge cell.
• Reaching the cell just before a pillar: If the next cell in the sliding direction contains a pillar, he cannot enter the cell with the pillar, so he stops at the cell just before it.

Here, up means the direction of decreasing row number, down means increasing row number, left means decreasing column number, and right means increasing column number.

If he cannot advance even one cell in the chosen direction (i.e., the adjacent cell contains a pillar, or he is already at the edge of the rink and no cell exists in that direction), Takahashi does not move and stays at his current cell. This still counts as one move.

Takahashi may visit the same cell any number of times.

Find the minimum number of moves required for Takahashi to start from coordinates (1, 1) and stop at coordinates (H, W). Stopping at coordinates (H, W) means that, following the movement rules described above, he comes to a stop at coordinates (H, W). Simply passing through coordinates (H, W) while sliding does not count as reaching the goal.

If it is impossible to reach the goal, output -1.

It is guaranteed that there are no pillars at coordinates (1, 1) or coordinates (H, W).

Constraints

• 2 \leq H \leq 100
• 2 \leq W \leq 100
• 0 \leq N \leq H \times W - 2
• 1 \leq R_i \leq H
• 1 \leq C_i \leq W
• (R_i, C_i) \neq (1, 1)
• (R_i, C_i) \neq (H, W)
• If i \neq j, then (R_i, C_i) \neq (R_j, C_j)
• All input values are integers

Sample Input 1

3 3 1
2 2

Sample Output 1

2

Sample Input 2

5 6 3
2 3
4 4
3 6

Sample Output 2

2

Sample Input 3

10 10 8
1 5
3 1
3 10
5 5
7 3
7 8
10 4
2 8

Sample Output 3

4

Problem Statement

Takahashi decided to select exactly K jewels from N jewels at a jewelry store to make a necklace. The jewels are numbered from 1 to N, and there is exactly one of each. The same jewel cannot be selected more than once.

Each jewel i (1 \leq i \leq N) has an integer value called "brilliance" P_i. Additionally, there is an integer value C_{i,j} representing the "harmony" when jewel i and jewel j are placed adjacent to each other. The harmony is symmetric, satisfying C_{i,j} = C_{j,i}.

Since a necklace is circular, the selected K jewels are arranged in a ring. The arrangement can be chosen freely. The "beauty" of the necklace is calculated as the sum of the following two values:

• The sum of the brilliance of each of the K selected jewels
• The sum of the harmony of all adjacent pairs of jewels on the necklace (there are exactly K adjacent pairs among the K jewels arranged in a ring)

For example, if K = 3 and jewels a, b, c are arranged in this order in a ring, the beauty is P_a + P_b + P_c + C_{a,b} + C_{b,c} + C_{c,a}.

Takahashi wants to maximize the beauty of the necklace. Select exactly K jewels from the N jewels and arrange them in an optimal circular order. Find the maximum value of the beauty.

Note that since C_{i,j} = C_{j,i}, circular arrangements that coincide by rotation or reflection have the same beauty. Therefore, there is no need to distinguish between them when finding the maximum value.

Constraints

• 3 \leq K \leq N \leq 16
• -10^6 \leq P_i \leq 10^6 (1 \leq i \leq N)
• -10^6 \leq C_{i,j} \leq 10^6 (1 \leq i, j \leq N)
• C_{i,j} = C_{j,i} (1 \leq i, j \leq N)
• C_{i,i} = 0 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

4 3
10 20 30 40
0 5 3 1
5 0 8 2
3 8 0 6
1 2 6 0

Sample Output 1

106

Sample Input 2

5 3
-10 -20 -30 -40 -50
0 -5 -3 -1 -2
-5 0 -8 -2 -4
-3 -8 0 -6 -1
-1 -2 -6 0 -3
-2 -4 -1 -3 0

Sample Output 2

-76

Sample Input 3

8 5
100 200 150 300 250 50 175 225
0 10 20 30 15 5 25 35
10 0 40 10 20 30 15 5
20 40 0 50 10 20 30 10
30 10 50 0 60 15 25 20
15 20 10 60 0 35 45 30
5 30 20 15 35 0 10 40
25 15 30 25 45 10 0 55
35 5 10 20 30 40 55 0

Sample Output 3

1325

Sample Input 4

12 8
500 -300 400 100 -200 600 350 -150 450 200 -100 300
0 50 -30 20 10 -40 60 15 -25 35 45 -10
50 0 40 -20 30 15 -35 25 50 -15 20 10
-30 40 0 55 -10 20 30 -45 15 25 -20 35
20 -20 55 0 45 -30 10 40 -15 50 30 -25
10 30 -10 45 0 25 -20 35 40 -30 15 50
-40 15 20 -30 25 0 50 -10 30 45 -35 20
60 -35 30 10 -20 50 0 40 -15 25 35 -30
15 25 -45 40 35 -10 40 0 50 -20 30 15
-25 50 15 -15 40 30 -15 50 0 45 -10 25
35 -15 25 50 -30 45 25 -20 45 0 40 -35
45 20 -20 30 15 -35 35 30 -10 40 0 50
-10 10 35 -25 50 20 -30 15 25 -35 50 0

Sample Output 4

3240

Sample Input 5

3 3
1000000 1000000 1000000
0 1000000 1000000
1000000 0 1000000
1000000 1000000 0

Sample Output 5

6000000