Problem Statement

Takahashi is a chef working in a restaurant kitchen.

Today, Takahashi needs to prepare N ingredients. The time required to prepare the i-th ingredient is T_i seconds. Takahashi can only prepare one ingredient at a time.

Additionally, according to the kitchen rules, Takahashi must take exactly M breaks during his work. Each break takes R seconds. A break can only be taken immediately after finishing the preparation of any ingredient (breaks cannot be taken before starting the first ingredient or after finishing the last ingredient).

Find the minimum total time from the start of work to the completion of all work, when preparing all ingredients and taking exactly M breaks. Note that the order in which ingredients are prepared can be freely chosen.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq N - 1
• 1 \leq R \leq 10^9
• 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 1 5
10 20 30

Sample Output 1

65

Sample Input 2

5 2 10
3 7 2 8 5

Sample Output 2

45

Sample Input 3

10 4 1000000000
100 200 300 400 500 600 700 800 900 1000

Sample Output 3

4000005500

Problem Statement

Takahashi is operating a sightseeing bus tour. In this tour, a bus picks up passengers while visiting multiple stops in order.

The tour has N stops, numbered stop 1, stop 2, ..., stop N in order from the departure point. Stop 1 is the first stop, and stop N is the final destination.

The bus is initially empty (before any boarding takes place at stop 1).

At each stop i (1 \leq i \leq N), A_i new passengers board the bus.

Furthermore, at each stop i (1 \leq i \leq N - 1), after boarding, B_i passengers get off the bus and leave the tour during the trip to the next stop i + 1. However, if the number of passengers currently on the bus is less than B_i, all passengers on the bus get off.

In summary, the process at each stop i is as follows:

1. A_i new passengers board the bus.
2. If i \leq N - 1, during the trip to the next stop, \min(\text{current number of passengers}, B_i) passengers get off. If i = N, no passengers get off.

Find the number of passengers on the bus when boarding at stop N is completed.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq B_i \leq 10^9 (1 \leq i \leq N - 1)
• All input values are integers.

Sample Input 1

3
5 2
3 1
4

Sample Output 1

9

Sample Input 2

3
2 10
1 5
3

Sample Output 2

3

Sample Input 3

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

Sample Output 3

13

Sample Input 4

10
1000000000 500000000
1000000000 200000000
500000000 1000000000
300000000 100000000
0 999999999
1000000000 1000000000
999999999 0
0 500000000
500000000 1000000000
123456789

Sample Output 4

123456789

Sample Input 5

2
0 0
0

Sample Output 5

0

Problem Statement

Takahashi works as a guide for a tour of a large factory.

The factory has N manufacturing areas, each numbered from 1 to N. Visiting each area i takes exactly T_i minutes.

Today, M tour groups will visit the factory. Each group j arrives at the factory at time S_j minutes, and immediately after arrival, they visit all areas with numbers from L_j to R_j. The group visits the areas one by one in order of increasing area number, and as soon as they finish visiting one area, they immediately begin visiting the next area (there is no travel time between areas).

Each area is spacious enough that even if multiple groups are visiting the same area at the same time, they do not affect each other.

Takahashi wants to calculate in advance the time at which each group finishes all their visits, and inform the groups.

For each group, determine the time (in minutes) at which they complete visiting all of their designated areas.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq T_i \leq 10^9
• 0 \leq S_j \leq 10^9
• 1 \leq L_j \leq R_j \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

60
95
150

Sample Input 2

4 5
15 25 10 30
0 1 4
10 1 1
20 2 3
0 3 4
50 1 2

Sample Output 2

80
25
55
40
90

Sample Input 3

10 6
100 200 300 150 250 50 400 100 350 200
0 1 10
1000 3 7
500 1 5
0 6 10
200 4 6
999999999 1 1

Sample Output 3

2100
2150
1500
1100
650
1000000099

Problem Statement

Takahashi works as a delivery person. Today, he has received N delivery requests.

If he accepts the i-th request (1 \leq i \leq N), he receives a reward of P_i yen, but incurs expenses of C_i yen for fuel and other costs. Therefore, the net profit from accepting the i-th request is P_i - C_i yen (the net profit can be negative). Additionally, the weight of the package for the i-th request is W_i. If he does not accept a request, no reward or expense is incurred for that request, and there is no need to carry the package.

Takahashi will choose to accept 0 or more requests from the N requests. Each request is either accepted or not accepted; the same request cannot be accepted multiple times. If no requests are selected, both the total weight and the total net profit are 0.

However, all packages from the selected requests must be loaded onto a truck and delivered in a single trip. Since the truck has a maximum capacity of S, the total weight of the packages from the selected requests must be at most S.

Furthermore, in order to pay this month's rent, the total net profit from the selected requests must be at least T.

To summarize, let A (A \subseteq \{1, 2, \ldots, N\}) be the set of selected requests. We want to find a selection of A that satisfies both of the following conditions:

• The total weight of the packages from the selected requests is at most S. That is, \displaystyle\sum_{i \in A} W_i \leq S
• The total net profit from the selected requests is at least T. That is, \displaystyle\sum_{i \in A} (P_i - C_i) \geq T

Determine whether such a set A exists. If it exists, output the minimum value of |A| among all sets A satisfying the conditions. If it does not exist, output -1.

Constraints

• 1 \leq N \leq 50
• 1 \leq S \leq 10^4
• 1 \leq T \leq 10^4
• 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq C_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq W_i \leq 10^4 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

4 8 10
8 3 3
7 4 4
12 4 5
3 5 2

Sample Output 1

2

Sample Input 2

5 10 20
8 3 5
6 4 6
9 5 7
5 2 4
7 6 3

Sample Output 2

-1

Sample Input 3

10 30 50
60 5 25
30 2 12
25 3 11
20 5 10
18 4 9
15 6 8
12 3 7
10 4 6
8 5 5
5 3 4

Sample Output 3

1

Problem Statement

Takahashi is working a part-time job at a moving company. Today's task is to transport N packages from the 1st floor of an apartment building to a single destination floor using an elevator.

Each package i (1 \leq i \leq N) has a weight of W_i kilograms. The elevator in this apartment building has a maximum total weight capacity of C kilograms for the packages loaded at one time. Takahashi rides the elevator alongside the packages to transport them, but his own body weight is not counted toward the weight capacity.

To finish the work efficiently, Takahashi decided to divide the N packages into several groups and transport each group together using the elevator. Here, each package belongs to exactly one group, and each group contains at least one package. Additionally, the total weight of the packages in each group must be at most C kilograms.

In one trip, Takahashi loads all packages belonging to one group onto the elevator and transports them from the 1st floor to the destination floor. To transport the next group, Takahashi returns to the 1st floor with the empty elevator. The number of trips equals the number of groups.

Find the minimum number of trips required to transport all the packages.

Note that it is guaranteed that the weight of every package is at most C, so any single package can be transported on its own.

Constraints

• 1 \leq N \leq 15
• 1 \leq C \leq 10^9
• 1 \leq W_i \leq C (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 10
4 5 6

Sample Output 1

2

Sample Input 2

5 100
30 50 40 20 60

Sample Output 2

2

Sample Input 3

8 1000
200 300 150 400 250 100 350 450

Sample Output 3

3