Problem Statement

Takahashi is a web service operations manager. His system has N servers, and a large-scale campaign spanning M days starts tomorrow.

During the campaign period, exactly 1 heavy processing request occurs each day. For each of the M days, Takahashi must assign that request to exactly 1 of the N servers. The same server may be chosen on multiple days.

Each server i (1 \leq i \leq N) has a "processing capacity" A_i. If the total number of requests assigned to server i throughout the entire campaign period is at most A_i, that server operates normally. On the other hand, if more than A_i requests are assigned to it, that server will go down. Takahashi must not let any server go down.

Can Takahashi choose request assignments wisely enough to get through the M-day campaign without any server going down?

If there exists an assignment that allows all M days to be completed without any server going down, output Yes; otherwise, output No.

Constraints

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

Sample Input 1

3 10
3 4 2

Sample Output 1

No

Sample Input 2

5 100
10 20 30 15 25

Sample Output 2

Yes

Sample Input 3

4 1000000000
250000000 250000000 250000000 250000000

Sample Output 3

Yes

Problem Statement

Takahashi aspires to become a pianist, and today he has decided to play N practice pieces in order from the 1-st to the N-th.

The i-th piece has an integer difficulty D_i. The time required to perform each piece is determined by the following rules:

• The 1-st piece takes D_1 minutes to perform.
• For the 2-nd piece onward (2 \leq i \leq N), the performance time depends on the relationship between the difficulty of the current piece and the immediately preceding piece.
• If the difficulty is strictly greater than the previous piece (D_{i-1} < D_i), then the previous piece served as a warm-up, so the time is reduced to \lfloor D_i / 2 \rfloor minutes. Here, \lfloor x \rfloor denotes the largest integer not exceeding x (that is, the value obtained by dividing D_i by 2 and rounding down).
• If the difficulty is less than or equal to the previous piece (D_{i-1} \geq D_i), no reduction is applied and the piece takes D_i minutes.

When Takahashi performs all pieces in order from the 1-st to the N-th, how many minutes does it take in total?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq D_i \leq 10^9
• All inputs are integers.

Sample Input 1

5
3 5 4 8 10

Sample Output 1

18

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

13

Sample Input 3

10
100 50 200 200 300 150 400 500 600 100

Sample Output 3

1600

Problem Statement

Takahashi is a mountain guide. In a certain mountainous region, N mountain huts are lined up in a row. The i-th mountain hut from the left (hereafter called hut i) is at an elevation of A_i meters.

Between adjacent mountain huts, trails are maintained only when the elevation difference is small. Specifically, for hut i and hut i+1, if the absolute difference in elevation is at most K (that is, |A_i - A_{i+1}| \leq K), there is a trail between them and one can travel directly between them. If the absolute difference in elevation is greater than K, there is no trail and one cannot travel directly between them. There are no trails between non-adjacent mountain huts.

A maximal set of mountain huts that can be reached from one another by following a sequence of trails is called an area. Since trails only exist between adjacent huts, the hut numbers belonging to each area always form a contiguous interval. Formally, an area is a contiguous interval [l, r] (1 \leq l \leq r \leq N) of hut numbers that satisfies both of the following conditions:

• There is a trail between all adjacent huts within the interval. That is, for all integers i such that l \leq i \leq r-1, |A_i - A_{i+1}| \leq K holds. (When l = r, this condition is automatically satisfied.)
• The interval is maximal. That is, if l \geq 2 then |A_{l-1} - A_l| > K, and if r \leq N-1 then |A_r - A_{r+1}| > K.

Each of the N mountain huts belongs to exactly one area.

Takahashi wants to answer Q questions. For the j-th question, determine whether hut L_j and hut R_j belong to the same area.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

6 3 3
10 13 15 25 27 26
1 3
2 5
4 6

Sample Output 1

Yes
No
Yes

Sample Input 2

9 5 5
100 102 110 112 111 105 103 200 198
1 2
1 3
3 5
6 9
8 9

Sample Output 2

Yes
No
Yes
No
Yes

Sample Input 3

12 4 6
50 52 54 56 100 98 96 94 92 90 50 52
1 4
1 5
5 10
10 11
11 12
3 12

Sample Output 3

Yes
No
Yes
No
Yes
No

Problem Statement

Takahashi works at a quarry. There are N rocks lined up in a row at the quarry, and he needs to destroy all of them.

The i-th rock has hardness H_i. Takahashi processes the rocks one by one in order from the 1-st rock to the N-th rock. He cannot move on to processing the next rock until the current rock is destroyed.

Each turn, Takahashi chooses and performs exactly one of the following two actions:

• Strike with a hammer: Reduce the hardness of the rock currently being processed by 1. This consumes 1 turn.
• Use dynamite: Instantly reduce the hardness of the rock currently being processed to 0. This consumes 1 turn. However, Takahashi only has K sticks of dynamite in total, and each use consumes 1 stick. This action cannot be chosen when he has 0 sticks remaining.

When a rock's hardness becomes 0, that rock is destroyed, and he moves on to processing the next rock. The work is complete once all rocks are destroyed.

Find the minimum number of turns required to destroy all rocks when Takahashi acts optimally.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N
• 1 \leq H_i \leq 10^9
• All inputs are integers

Sample Input 1

3 1
5 2 8

Sample Output 1

8

Sample Input 2

5 2
10 3 7 4 6

Sample Output 2

15

Sample Input 3

8 3
100 5 200 8 150 3 50 300

Sample Output 3

169

Problem Statement

Takahashi is in charge of organizing an exhibition where N companies are exhibiting. The venue has N booths arranged in a circle, numbered 1 to N in clockwise order. Due to the circular arrangement, booth k and booth k+1 (1 \leq k \leq N-1) are adjacent, and booth N and booth 1 are also adjacent. Therefore, there are exactly N pairs of adjacent booths.

The N companies are also numbered 1 to N, and initially, company i is placed in booth i (1 \leq i \leq N). Each booth contains exactly one company, and each company uses exactly one booth.

At the exhibition, for each pair of adjacent booths, the two companies placed there will hold a collaboration event. The audience-drawing effect when company i and company j collaborate is represented by C_{i,j} (C_{i,j} = C_{j,i}).

Takahashi can perform the following operation 0 or more times, up to K times: choose two distinct companies and swap the booths they are currently using. There are no restrictions on which two companies are chosen for each operation; a company may be chosen in multiple operations, and the same pair of companies may be chosen multiple times.

Consider the arrangement after all operations are completed. Let p_k denote the company placed in booth k after the operations. Then (p_1, p_2, \ldots, p_N) is a permutation of (1, 2, \ldots, N). The total audience-drawing effect over all N pairs of adjacent booths is

$\sum_{k=1}^{N-1} C_{p_k, p_{k+1}} + C_{p_N, p_1}$

Find the maximum value of this total when the operations are chosen optimally.

Constraints

• 3 \leq N \leq 8
• 0 \leq K \leq \frac{N(N-1)}{2}
• 0 \leq C_{i,j} \leq 10^6
• C_{i,j} = C_{j,i}
• C_{i,i} = 0
• All inputs are integers

Sample Input 1

3 0
0 10 30
10 0 20
30 20 0

Sample Output 1

60

Sample Input 2

4 1
0 5 50 100
5 0 5 100
50 5 0 50
100 100 50 0

Sample Output 2

255

Sample Input 3

6 3
0 10 80 50 30 100
10 0 90 20 70 40
80 90 0 60 10 50
50 20 60 0 100 30
30 70 10 100 0 80
100 40 50 30 80 0

Sample Output 3

470