Problem Statement

Takahashi has a part-time job organizing bookshelves at a library.

He needs to arrange N books in a row on a bookshelf. Each book has a unique number from 1 to N, and book i has a thickness of D_i centimeters.

A bookend (with width S centimeters) is fixed at the left end of the bookshelf. All N books are to be placed in a row from left to right, to the right of this bookend. There is no restriction on the right end of the bookshelf, and it can be assumed to be sufficiently long.

According to the library's rules, to prevent damage to the books, there must be a gap of at least K centimeters between any two adjacent books. Additionally, there must be a gap of at least K centimeters between the bookend and the leftmost book. Here, the gap between two objects refers to the distance from the right edge of the left object to the left edge of the right object.

Takahashi can arrange all N books exactly once each, in any order he likes. After all books have been placed, find the minimum possible distance from the left edge of the bookend to the right edge of the rightmost book.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq S \leq 10^9
• 1 \leq K \leq 10^9
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 2 1
3 1 2

Sample Output 1

11

Sample Input 2

1 5 3
4

Sample Output 2

12

Sample Input 3

5 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

11000000000

Problem Statement

Takahashi is working on organizing strings.

Takahashi can perform the following operation on a string zero or more times:

• Choose one pair of adjacent identical characters (for example, aa or bb) in the string, and remove those 2 characters from the string. After removal, the remaining left and right parts are concatenated as they are.

For example, given the string abba, removing the adjacent bb yields aa, and further removing aa yields the empty string.

You are given a string S consisting of lowercase English letters. Find the minimum possible length of the string obtained after performing the operation repeatedly.

Constraints

• 1 \leq |S| \leq 10^6 (|S| denotes the length of string S)
• S is a string consisting of lowercase English letters.

Sample Input 1

abba

Sample Output 1

0

Sample Input 2

abcde

Sample Output 2

5

Sample Input 3

abbacaaccbbddeeffeedcba

Sample Output 3

5

Sample Input 4

aaabccddddeeffffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwxxxyyyzzz

Sample Output 4

22

Sample Input 5

a

Sample Output 5

1

Problem Statement

Takahashi operates a system that manages membership registration for N customers.

Each customer is assigned a number from 1 to N, and customer i has a priority A_i. All customers have distinct priorities. A larger priority value means a higher priority.

There are M shops, each numbered from 1 to M. Shop j has a membership capacity C_j, which represents the maximum number of members that can be registered at that shop simultaneously.

Initially, no customer is registered at any shop. From now on, Q applications will be processed in order. Each customer submits at most one application (that is, all applicants across different applications are distinct). In the k-th application, customer P_k requests membership registration at shop D_k.

When an application is processed, the following rules apply:

• If the current number of members at the shop is less than the capacity C_{D_k}, customer P_k is registered as a member of that shop.
• If the current number of members at the shop equals the capacity C_{D_k} (i.e., the shop is full), the priority of the applying customer P_k is compared with that of the member currently registered at the shop who has the lowest priority. Since all customers have distinct priorities, the member with the lowest priority is uniquely determined.
• If the applying customer's priority is higher, the member with the lowest priority is unregistered (returning to a state of not being registered at any shop), and the applying customer is newly registered as a member of that shop.
• Otherwise (if the applying customer's priority is lower), the application is rejected. The applying customer remains unregistered at any shop, and the shop's members remain unchanged.

By the above rules, the number of members at each shop never exceeds its capacity at any point. Also, since each customer submits at most one application, no customer is ever registered at multiple shops simultaneously.

After all applications have been processed, determine the number of members registered at each shop.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• A_i \neq A_j (i \neq j)
• 1 \leq C_j \leq N (1 \leq j \leq M)
• 1 \leq P_k \leq N (1 \leq k \leq Q)
• 1 \leq D_k \leq M (1 \leq k \leq Q)
• P_k \neq P_l (k \neq l) (that is, each customer submits at most one application)
• All input values are integers

Sample Input 1

5 2 5
10 30 20 50 40
2 1
1 1
2 1
3 1
4 2
5 2

Sample Output 1

2 1

Sample Input 2

7 3 7
5 15 25 35 45 55 3
2 2 1
7 1
1 1
3 1
2 2
4 2
5 2
6 3

Sample Output 2

2 2 1

Sample Input 3

10 4 10
100 90 80 70 60 50 40 30 20 10
3 2 2 1
8 1
10 1
9 1
7 1
5 2
6 2
3 2
4 3
2 3
1 4

Sample Output 3

3 2 2 1

Problem Statement

Takahashi runs a jewelry store. He is trying to select jewels to exhibit at an upcoming jewelry exhibition.

The store has N types of jewels, and each jewel i has a value B_i and a weight W_i. There is an upper limit C on the total weight of jewels that can be brought to the exhibition venue, and jewels exceeding this weight cannot be brought in.

Takahashi has K special weight-reduction cases. By using one weight-reduction case, he can halve the weight of one type of jewel (rounded down to the nearest integer). However, multiple cases cannot be used on the same jewel.

Takahashi can bring at most one jewel of each type. He wants to maximize the total value of the jewels he brings.

Find the maximum total value of jewels that can be brought when the weight-reduction cases are used optimally.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq C \leq 10^5
• 0 \leq K \leq \min(N, 30)
• N(K+1)(C+1) \leq 2 \times 10^7
• 1 \leq B_i \leq 10^9
• 1 \leq W_i \leq 2C
• All inputs are integers

Sample Input 1

4 10 1
8 6
10 7
5 4
6 5

Sample Output 1

18

Sample Input 2

5 12 0
7 3
12 8
9 5
4 6
11 10

Sample Output 2

19

Sample Input 3

12 50 3
30 18
45 27
25 15
60 40
35 22
50 35
20 12
55 45
40 30
15 10
70 55
28 16

Sample Output 3

155

Sample Input 4

40 300 6
120 80
250 180
90 60
310 240
180 130
400 350
75 45
220 170
500 420
160 110
330 260
140 90
270 200
600 500
95 70
210 160
450 380
125 85
360 290
280 210
510 460
170 125
390 310
240 190
700 590
155 100
430 330
105 75
320 250
260 205
540 440
190 140
470 360
115 95
350 270
290 230
620 520
200 150
410 340
130 105

Sample Output 4

885

Sample Input 5

1 1 1
1000000000 2

Sample Output 5

1000000000

Problem Statement

Takahashi has a job where he processes N tasks in order.

For the i-th task, an integer A_i representing the workload and an integer B_i representing the recovery from a break are defined.

Takahashi's stress level is managed as a non-negative integer G (initially 0), and the number of times he has reached his limit is managed as a non-negative integer C (initially 0). When processing task i, the following operations are performed in order of steps 1, 2, 3.

1. Due to the task's workload, the stress level increases by A_i. That is, G is updated to G + A_i.
2. Due to the break after the task, the stress level decreases by B_i. However, the stress level does not go below 0. That is, G is updated to \max(0, G - B_i).
3. At this point, if G \geq K, Takahashi reaches his limit. C is updated to C + 1, and G is updated to 0. If G < K, nothing happens.

After step 3 is completed (whether or not he reached his limit), he proceeds to process the next task.

Aoki asks Q questions of the form "What would happen if only a portion of the task sequence were processed?"

In the j-th question, integers L_j and R_j are given.

Starting from G = 0, C = 0, determine the number of times the limit was reached C and the stress level G after all tasks L_j, L_j + 1, \ldots, R_j have been processed (through step 3) in this order.

Each question is independent. The result of one question does not affect another question.

Constraints

• 1 \leq N \leq 6 \times 10^4
• 1 \leq K \leq 300
• 1 \leq Q \leq 6 \times 10^4
• 1 \leq A_i \leq 10^9
• 0 \leq B_i \leq 10^9
• 1 \leq L_j \leq R_j \leq N
• All inputs are integers.

Sample Input 1

5 10 4
6 2
4 1
8 0
3 5
10 3
1 3
2 4
4 5
3 3

Sample Output 1

1 0
1 0
0 7
0 8

Sample Input 2

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

Sample Output 2

0 1
0 0
1 0
1 4
0 4

Sample Input 3

15 20 10
7 3
12 5
4 10
25 0
3 1
18 4
6 6
30 15
9 0
2 8
14 2
5 20
21 1
8 7
11 0
1 5
2 8
4 4
6 10
1 15
9 15
11 13
3 12
7 14
10 10

Sample Output 3

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

Sample Input 4

40 300 25
120 30
250 100
80 0
500 250
40 60
1000 800
299 0
1 0
600 350
75 75
310 10
20 5
450 200
90 10
200 50
150 200
700 401
60 0
30 100
1000000000 999999900
5 0
295 10
400 120
55 55
180 30
240 100
360 80
15 0
90 20
600 600
280 0
35 10
100 0
500 260
70 30
330 40
10 100
220 10
410 200
50 0
1 10
5 15
10 20
15 25
20 30
25 35
30 40
1 40
7 7
11 18
19 22
23 29
31 36
34 40
2 39
4 13
8 27
12 32
16 16
20 20
21 40
1 1
40 40
6 24
14 38

Sample Output 4

3 250
3 150
3 100
3 0
3 85
3 40
4 50
13 50
0 299
3 60
1 0
2 85
3 0
2 50
12 0
3 265
6 0
6 25
0 0
0 100
6 50
0 90
0 50
5 280
7 210

Sample Input 5

1 300 1
1000000000 999999700
1 1

Sample Output 5

1 0