Problem Statement

Takahashi is preparing N types of exercises for strength training. Each exercise is numbered from 1 to N, and exercise i has an initial stamina value of A_i.

Each exercise has a remaining stamina value. Before training begins, the remaining stamina of exercise i is equal to its initial value A_i.

Every day, Takahashi performs training exactly once according to the following procedure:

1. From the N types of exercises, choose one whose remaining stamina is at least K. As long as the remaining stamina is at least K, an exercise can be chosen again regardless of how many times it has been chosen in the past.
2. Decrease the remaining stamina of the chosen exercise by exactly K. The remaining stamina of exercises that were not chosen does not change.

In step 1, if there is no exercise with remaining stamina of at least K, training cannot be performed that day, and no further training can be done from that point onward.

Takahashi is planning M days of training. That is, he needs to perform the above procedure a total of M times.

Determine whether Takahashi can complete training on all M days by choosing exercises wisely. If it is possible, output Yes; otherwise, output No.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^9
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 5 2
4 3 5

Sample Output 1

Yes

Sample Input 2

3 6 2
4 3 5

Sample Output 2

No

Sample Input 3

5 5 1000000000
1000000000 1000000000 1000000000 999999999 1000000000

Sample Output 3

No

Problem Statement

Takahashi is driving on a highway to reach his destination.

Along this highway, there are N toll booths placed in order between the entrance and the destination. The i-th toll booth is located at a distance of D_i meters from the entrance. The destination is located at a distance of G meters from the entrance, and it is farther from the entrance than all toll booths.

Takahashi's car always travels at a constant speed of 1 meter per second. When he reaches a toll booth, he must stop and pay the toll; at the i-th toll booth, it takes T_i seconds from stopping to completing the payment and departing again. He does not stop anywhere other than at toll booths.

Takahashi has an ETC card and must set exactly one ETC usage section. Specifically, he chooses an integer i (1 \leq i \leq N-K+1) and designates exactly K consecutively numbered toll booths from the i-th to the (i+K-1)-th as the ETC usage section. At the K toll booths designated as the ETC usage section, he can pass through without stopping, incurring no payment time. At all other toll booths, he stops and pays as usual.

The time it takes for Takahashi to travel from the highway entrance to the destination is the sum of the travel time (since the distance from the entrance to the destination is G meters and the speed is 1 meter per second, this is G seconds) and the total payment time at all toll booths outside the ETC usage section. Find the minimum possible total time when the ETC usage section is chosen optimally.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq G \leq 10^9
• 1 \leq D_i < G (1 \leq i \leq N)
• D_1 < D_2 < \cdots < D_N
• 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 2 100
10 5
30 10
60 3

Sample Output 1

103

Sample Input 2

5 3 1000
100 20
200 50
400 30
600 40
800 10

Sample Output 2

1030

Sample Input 3

7 4 500000000
1000 100000000
50000 200000000
100000 150000000
200000 300000000
300000 50000000
400000 250000000
450000 100000000

Sample Output 3

900000000

Problem Statement

Takahashi is at an izakaya (Japanese-style pub). The menu has N dishes, and the i-th dish has a "deliciousness" value A_i and a "richness" value B_i. Takahashi can order any combination of these dishes. Each dish can be ordered at most once, and it is also allowed to order no dishes at all (in which case, the satisfaction is 0).

Takahashi likes rich dishes, but if the total richness of the ordered dishes exceeds K, his satisfaction decreases by D for each unit of excess richness.

Specifically, Takahashi's final satisfaction is calculated by the following formula:

\text{Satisfaction} = \left(\text{Total deliciousness of ordered dishes}\right) - D \times \max\!\left(0,\ \text{Total richness of ordered dishes} - K\right)

Find the maximum satisfaction Takahashi can achieve.

Constraints

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

Sample Input 1

3 5 2
4 2
5 3
10 6

Sample Output 1

9

Sample Input 2

2 1 10
3 5
4 6

Sample Output 2

0

Sample Input 3

8 15 3
10 4
7 5
8 6
14 8
5 3
11 7
6 2
13 9

Sample Output 3

30

Sample Input 4

19 50 4
12 5
7 4
20 10
18 9
5 2
11 6
9 5
14 7
6 3
25 13
8 4
16 8
10 6
13 7
21 11
4 1
17 9
15 8
19 10

Sample Output 4

104

Sample Input 5

1 1 1000000
1000000 1000000

Sample Output 5

0

Problem Statement

Takahashi is analyzing the log of a communication system. In this system, a bit string S of length N consisting only of 0 and 1 is recorded.

Takahashi wants to find pairs of "nearly identical" intervals in this signal log.

A contiguous substring of S is represented by a pair of starting position l and ending position r, denoted (l, r) (1 \leq l \leq r \leq N). This refers to the contiguous portion from the l-th character to the r-th character of S, and its length is r - l + 1.

A pair of two contiguous substrings ((l_1, r_1), (l_2, r_2)) is called a "nearly identical" pair if and only if all of the following conditions are satisfied:

• (l_1, r_1) \neq (l_2, r_2). That is, l_1 \neq l_2 or r_1 \neq r_2.
• r_1 - l_1 = r_2 - l_2. That is, the two contiguous substrings have equal length.
• Let L be the length of the two contiguous substrings. When comparing the i-th characters from the beginning (1 \leq i \leq L), there is exactly 1 position i where the characters differ (that is, the Hamming distance is exactly 1).

Pairs are counted as unordered. That is, ((l_1, r_1), (l_2, r_2)) and ((l_2, r_2), (l_1, r_1)) are considered the same pair.

Note that substrings are distinguished by their position pair (l, r). Even if the actual string contents are identical, if (l_1, r_1) \neq (l_2, r_2), they are treated as different substrings.

Find the number of pairs that satisfy the conditions.

Constraints

• 1 \leq N \leq 5000
• N is an integer.
• S is a string of length N consisting only of 0 and 1.

Sample Input 1

3
101

Sample Output 1

2

Sample Input 2

4
0011

Sample Output 2

7

Sample Input 3

20
01101001011010010110

Sample Output 3

298

Sample Input 4

50
01001101011010001001110101100110100101101001101011

Sample Output 4

2136

Sample Input 5

1
0

Sample Output 5

0

Problem Statement

Takahashi is an engineer at a telecommunications company, responsible for investigating radio conditions along a road.

The road under investigation is a straight line, and N radio towers are built along the road. The road is represented as a number line, where the i-th radio tower is located at coordinate X_i and has power output B_i.

The "signal strength" at coordinate p is defined as the sum of contributions from all radio towers:

f(p) = \sum_{i=1}^{N} \max(0,\ B_i - |p - X_i|)

That is, each radio tower i delivers a signal strength of \max(0,\ B_i - |p - X_i|) to coordinate p. The signal weakens as one moves farther from the tower, and it no longer reaches once the distance is at least B_i.

Takahashi's colleague Aoki will conduct signal strength surveys for Q intervals. For each survey j, an interval [L_j, R_j] is given. Find the maximum value of f(p) over all integer coordinates p within that interval.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 0 \leq X_i \leq 2 \times 10^5
• 1 \leq B_i \leq 2 \times 10^5
• 0 \leq L_j \leq R_j \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

1 2
5 3
0 10
0 3

Sample Output 1

3
1

Sample Input 2

3 3
2 3
5 4
10 2
0 10
6 10
9 12

Sample Output 2

4
3
2

Sample Input 3

5 5
0 5
10 3
20 8
15 6
25 4
0 30
12 18
0 5
20 25
0 0

Sample Output 3

9
9
5
9
5