Problem Statement

Takahashi is a manager in charge of N projects. Each project has already been allocated a budget, but during the end-of-term review, it was discovered that some projects had been allocated too much budget.

The i-th project (1 \leq i \leq N) has been allocated a budget of A_i ten-thousand yen, and the appropriate budget amount is B_i ten-thousand yen. When A_i > B_i, that project is over budget, and A_i - B_i ten-thousand yen must be returned. When A_i \leq B_i, that project is not over budget, and no return is necessary.

Find the number of projects that are over budget and the total amount of money (in ten-thousand yen) that needs to be returned.

Constraints

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

Sample Input 1

3
100 80
50 50
30 60

Sample Output 1

1 20

Sample Input 2

5
500 300
200 400
150 100
600 600
800 350

Sample Output 2

3 700

Sample Input 3

10
1000000000 999999999
500000000 500000000
300000000 100000000
750000000 800000000
999999999 1
100 200
450000000 300000000
600000000 600000001
1 1000000000
888888888 777777777

Sample Output 3

5 1461111110

Problem Statement

Takahashi has to take exams in N subjects. For each subject i (1 \leq i \leq N), he can currently score A_i points with his present ability. Takahashi needs to score at least the passing mark T in every subject.

By studying additionally, Takahashi can raise his score in each subject. To raise the score in subject i by 1 point, C_i hours of study are required. That is, to raise the score in subject i by k points, k \times C_i hours of study are required. Note that he cannot lower his score.

For subjects where his current score is already T or higher, no additional study is needed, and the study time for that subject is 0.

Find the minimum total study time required for Takahashi to bring his score in every subject to T or higher.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T \leq 10^4
• 0 \leq A_i \leq 10^4
• 1 \leq C_i \leq 10^4
• All input values are integers.

Sample Input 1

3 60
50 3
70 2
40 5

Sample Output 1

130

Sample Input 2

5 80
75 2
100 6
60 4
50 1
80 3

Sample Output 2

120

Sample Input 3

10 100
100 8
90 5
150 3
30 2
100 10
99 100
0 1
9999 4
50 3
85 7

Sample Output 3

645

Problem Statement

Takahashi has come to a souvenir shop to buy souvenirs from his trip. The shop has N sweets lined up, each with a set price and deliciousness.

The sweets are numbered from 1 to N. Sweet i has a price of P_i yen and a deliciousness of S_i.

Takahashi wants to choose exactly 1 sweet as a souvenir for his friend Aoki, satisfying all of the following conditions:

• The price is at least L yen and at most R yen.
• The deliciousness is at least T.

If there exists at least one sweet satisfying the conditions, he will choose exactly 1 sweet from among them according to the following priorities:

• Prefer the one with the lowest price (smallest P_i).
• If there are multiple sweets with the same price, prefer the one with the highest deliciousness (largest S_i).
• If there are multiple sweets with the same price and the same deliciousness, prefer the one with the smallest number.

Since the sweet numbers from 1 to N are all distinct, the sweet chosen by these priorities is uniquely determined. Output the number of the chosen sweet.

If no sweet satisfies the conditions, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L \leq R \leq 10^9
• 1 \leq T \leq 10^9
• 1 \leq P_i \leq 10^9 （ 1 \leq i \leq N ）
• 1 \leq S_i \leq 10^9 （ 1 \leq i \leq N ）
• All inputs are integers.

Sample Input 1

5 100 500 3
150 5
200 8
50 10
150 4
600 9

Sample Output 1

1

Sample Input 2

4 300 500 7
100 10
400 3
600 8
350 5

Sample Output 2

-1

Sample Input 3

10 200 800 5
500 3
1000 10
250 9
300 6
150 8
800 5
250 9
400 7
900 12
600 4

Sample Output 3

3

Problem Statement

Takahashi is a delivery worker who visits N warehouses arranged in a row, collecting packages in order. The warehouses are numbered 1, 2, \ldots, N from west to east, and warehouse i contains a package of weight A_i.

Takahashi starts at some warehouse s (1 \leq s \leq N) carrying no packages, and visits warehouses sequentially heading east. Each time he visits a warehouse, he picks up the package there and adds it to his load. He keeps all packages he has picked up.

Specifically, at each warehouse, he follows these steps:

1. Pick up the package at that warehouse and add it to his load.
2. Check the total weight of his load (including the package just picked up).
3. If the total weight is greater than K (i.e., exceeds K), Takahashi cannot proceed further and stops at that warehouse.
4. If the total weight is at most K and the current warehouse is not warehouse N, he moves to the next warehouse (the neighboring warehouse to the east) and returns to step 1.
5. If the total weight is at most K and the current warehouse is warehouse N, there are no more warehouses to the east, so he stops at that warehouse.

In other words, when starting from warehouse s, Takahashi visits warehouses s, s+1, s+2, \ldots in order, and stops at warehouse t where the cumulative package weight A_s + A_{s+1} + \cdots + A_t first exceeds K. If he reaches warehouse N without exceeding K, he stops at warehouse N.

Define f(s) as the number of the warehouse where Takahashi stops.

Takahashi wants to answer Q questions. In the j-th question, integers L_j, R_j representing a range of starting points are given. Find the value of f(L_j) + f(L_j + 1) + \cdots + f(R_j).

Constraints

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

Sample Input 1

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

Sample Output 1

23
13
15

Sample Input 2

4 5 2
3 3 3 3
1 4
2 3

Sample Output 2

13
7

Sample Input 3

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

Sample Output 3

78
39
4
56

Sample Input 4

15 20 5
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5
1 15
5 10
1 5
10 15
8 12

Sample Output 4

164
62
35
90
67

Sample Input 5

1 1000000000000000 1
1
1 1

Sample Output 5

1

Problem Statement

Takahashi is traveling in a city with N sightseeing spots. The sightseeing spots are numbered from 1 to N, and there are M bidirectional roads connecting them.

Each sightseeing spot i has a positive integer value P_i called "satisfaction." Takahashi starts from sightseeing spot S, where his hotel is located, and heads to his destination, sightseeing spot T.

Road j bidirectionally connects sightseeing spots U_j and V_j, and costs a transportation fee of W_j regardless of the direction of travel.

Takahashi departs from sightseeing spot S and follows roads sequentially to arrive at sightseeing spot T. He may pass through the same road or the same sightseeing spot any number of times.

Takahashi's "profit" is defined as follows:

• Consider the set of all sightseeing spots visited along the route, including the starting point S and the destination T. The profit is the sum of the satisfaction values of each sightseeing spot in this set (counted once each) minus the total transportation fees of all roads traversed along the route.
• Even if the same sightseeing spot is visited multiple times, its satisfaction value is added only once.
• If the same road is traversed multiple times, the transportation fee is added for each traversal. Regardless of the direction of travel, each traversal of a road incurs one transportation fee.

Find the maximum profit when Takahashi travels from sightseeing spot S to sightseeing spot T.

Note that traversing roads unnecessarily only increases transportation fees without increasing satisfaction, so the maximum profit is always finite. Be aware that the maximum profit may be negative. It is guaranteed that T is reachable from S.

Constraints

• 2 \leq N \leq 12
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq S \leq N
• 1 \leq T \leq N
• S \neq T
• 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
• 1 \leq W_j \leq 10^4 (1 \leq j \leq M)
• There is at most one road connecting any pair of sightseeing spots.
• Sightseeing spot T is reachable from sightseeing spot S.
• All input values are integers.

Sample Input 1

3 3
10 20 30
1 3
1 2 5
2 3 5
1 3 25

Sample Output 1

50

Sample Input 2

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

Sample Output 2

126

Sample Input 3

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

Sample Output 3

294