Problem Statement

Takahashi is running a booth at a flea market. His booth sells N types of products, and the price of the i-th product (1 \leq i \leq N) is P_i yen. Assume that the stock of each product is sufficient.

During the event, M customers made purchases at Takahashi's booth. The j-th customer (1 \leq j \leq M) purchased Q_j units of the T_j-th product.

Takahashi initially has S yen in cash. Transactions with customers are processed one by one in order, starting from the 1st customer. The transaction with the j-th customer proceeds as follows, in this order:

1. Calculate the sales amount X = P_{T_j} \times Q_j yen.
2. As payment from the customer, X yen is added to Takahashi's cash on hand.
3. As a sales commission to the event organizer, \lfloor X / 2 \rfloor yen is deducted from his cash on hand. Here, \lfloor a \rfloor denotes the largest integer not exceeding the real number a.

In each transaction, the commission \lfloor X / 2 \rfloor is at most the sales amount X, so the net change in cash from a transaction is non-negative. Therefore, the cash on hand never becomes negative during the process of transactions.

After all transactions with the M customers have been completed, how many yen does Takahashi have on hand?

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 0 \leq S \leq 10^9
• 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq T_j \leq N (1 \leq j \leq M)
• 1 \leq Q_j \leq 10^4 (1 \leq j \leq M)
• All input values are integers
• It is guaranteed that the answer is between 0 and 10^{13}, inclusive

Sample Input 1

3 2 100
200 500 300
1 2
3 1

Sample Output 1

450

Sample Input 2

5 4 1000
150 300 99 500 1200
3 3
5 1
1 5
2 2

Sample Output 2

2424

Sample Input 3

6 5 0
1 9999 5000 3 7777 10000
2 10000
4 1
6 9999
1 1
5 5000

Sample Output 3

119432503

Problem Statement

Takahashi is going to distribute sweets to M children. The children are numbered from 1 to M. There are S sweets in total.

Each child i (1 \leq i \leq M) already has B_i sweets before the distribution.

The rules of distribution are as follows:

• Let q = \lfloor S / M \rfloor be the quotient and r = S \mod M be the remainder when S is divided by M.
• Give q sweets to every child.
• Additionally, distribute the remaining r sweets one by one to the children in order of their numbers, starting from the smallest. That is, children 1, 2, \ldots, r each receive one additional sweet (if r = 0, no additional distribution is performed).

As a result, the number of sweets child i receives in this distribution is q + 1 if i \leq r, and q if i > r.

The final number of sweets for child i is defined as the sum of the B_i sweets they originally had and the number they received in this distribution.

Takahashi must answer N questions from Aoki. For the j-th question (1 \leq j \leq N), find the sum of the final number of sweets for children from child L_j to child R_j (inclusive).

Output the answer for each of the N questions.

Constraints

• 1 \leq M \leq 2 \times 10^5
• 0 \leq S \leq 10^{9}
• 0 \leq B_i \leq 10^{9} (1 \leq i \leq M)
• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_j \leq R_j \leq M (1 \leq j \leq N)
• All inputs are integers.

Sample Input 1

5 13
1 2 3 4 5
3
1 5
2 4
1 3

Sample Output 1

28
17
15

Sample Input 2

3 0
5 10 15
3
1 3
1 1
2 3

Sample Output 2

30
5
25

Sample Input 3

8 25
10 20 30 40 50 60 70 80
5
1 8
1 1
3 7
1 4
5 8

Sample Output 3

385
14
265
113
272

Sample Input 4

10 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
6
1 10
1 1
1 5
6 10
3 7
10 10

Sample Output 4

11000000000
1100000000
5500000000
5500000000
5500000000
1100000000

Sample Input 5

1 1000000000
1000000000
1
1 1

Sample Output 5

2000000000

Problem Statement

Takahashi is helping with the apple harvest at an orchard. The orchard has N apple trees lined up in a straight line, each planted at a distinct position. The i-th tree is located at coordinate X_i on the number line.

Takahashi uses a harvesting cart to collect apples. The cart can be parked spanning an interval [L, R] (L \leq R) on the number line, and he can harvest apples from all trees within that interval. However, there is a limit on the range the cart can cover: the length of the interval R - L must be at most K.

Takahashi wants to choose a single interval of length at most K to park the cart and harvest apples from as many trees as possible.

A tree i is within the interval [L, R] if and only if L \leq X_i \leq R.

Determine the maximum number of trees from which apples can be harvested.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 0 \leq X_i \leq 10^9
• X_i \neq X_j (i \neq j)
• All inputs are integers

Sample Input 1

5 3
1 5 2 8 4

Sample Output 1

3

Sample Input 2

8 10
3 15 7 25 12 30 8 20

Sample Output 2

4

Sample Input 3

12 100
50 200 75 300 120 80 450 90 500 110 85 95

Sample Output 3

8

Problem Statement

Takahashi is attempting to cross a desert along a single road by car. Takahashi is currently at point 0 and needs to reach an oasis at point G. Here, point x represents the position at distance x from the starting point.

Takahashi's car initially contains F liters of fuel. The car can travel a distance of 1 using 1 liter of fuel, and cannot proceed further once the fuel runs out. Takahashi can only travel in one direction from point 0 toward point G and cannot turn back. Arriving at point G with exactly 0 fuel remaining is still considered as having reached the destination.

There are N gas stations between point 0 and point G. The i-th gas station is located at point P_i (0 < P_i < G) and can refuel R_i liters of fuel. For each gas station, Takahashi can choose to either stop by or pass through. If he stops by, R_i liters are added to his current fuel. He can stop at each gas station at most once. Additionally, if he stops by, he must refuel the full R_i liters (partial refueling is not possible). Note that there is no upper limit on the car's fuel tank capacity, so there is no problem regardless of how much fuel increases through refueling. Even if Takahashi arrives at a gas station's location with exactly 0 fuel, he can still stop at that gas station.

Find the minimum number of gas stations Takahashi needs to stop at in order to reach the oasis at point G. If it is impossible to reach point G regardless of which gas stations he stops at, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq G \leq 10^9
• 0 \leq F \leq 10^9
• 1 \leq P_i < G (1 \leq i \leq N)
• 1 \leq R_i \leq 10^9 (1 \leq i \leq N)
• P_i \neq P_j (i \neq j)
• All inputs are integers

Sample Input 1

3 10 4
4 3
6 2
7 3

Sample Output 1

2

Sample Input 2

3 15 4
3 2
6 1
10 10

Sample Output 2

-1

Sample Input 3

8 60 15
10 10
14 5
20 12
25 8
32 15
40 4
45 10
52 8

Sample Output 3

4

Sample Input 4

15 120 20
58 4
8 6
90 6
35 12
107 5
18 15
73 8
50 20
13 4
98 15
42 7
81 9
27 5
65 10
113 10

Sample Output 4

9

Sample Input 5

1 2 2
1 1

Sample Output 5

0

Problem Statement

Takahashi is analyzing personnel data of a certain company. The company has N employees, and each employee is assigned a workplace represented as a point on a number line. The workplace coordinate of the i-th employee is X_i, and their evaluation score is V_i. All X_i are distinct. A higher evaluation score represents a better evaluation.

Takahashi has received Q investigation requests. The j-th investigation specifies a range of workplace coordinates [L_j, R_j].

For each investigation j, let S_j be the set of employees whose workplace coordinates are at least L_j and at most R_j. For each employee in S_j, their "rank" is determined as follows:

• Let k be the number of employees in S_j whose evaluation score is strictly greater than that employee's evaluation score. Then that employee's rank is k + 1.

In other words, if multiple employees have the same evaluation score, they all receive the same rank (this is the so-called "standard competition ranking" method).

Example: Consider an investigation where S_j contains 3 employees with evaluation scores 5, 5, 3.

• The 2 employees with evaluation score 5 each have 0 employees in S_j with a strictly greater evaluation score, so their ranks are 0 + 1 = 1 each.
• The 1 employee with evaluation score 3 has 2 employees in S_j with a strictly greater evaluation score, so their rank is 2 + 1 = 3.

Thus, the ranks of the 3 employees are 1, 1, 3 respectively, and the sum of ranks is 1 + 1 + 3 = 5.

For each investigation, find the sum of ranks of all employees in S_j. If S_j is empty (no employees are within the range), the sum is 0.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq X_i \leq 10^9
• 1 \leq V_i \leq 10^9
• 1 \leq L_j \leq R_j \leq 10^9
• All X_i are distinct
• V_i are not necessarily distinct
• All input values are integers

Sample Input 1

3 3
1 5
2 5
3 3
1 3
2 3
1 1

Sample Output 1

5
3
1

Sample Input 2

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

Sample Output 2

3
0
9

Sample Input 3

8 5
2 7
4 3
6 7
8 5
10 3
12 9
14 7
16 1
1 16
4 12
6 6
3 9
1 2

Sample Output 3

32
14
1
6
1

Sample Input 4

10 8
5 100
11 50
17 100
23 75
29 50
35 200
41 75
47 100
53 50
59 200
1 59
5 35
20 50
11 47
35 59
1 10
29 29
17 41

Sample Output 4

47
19
14
25
14
1
1
14

Sample Input 5

1 1
1000000000 1000000000
1000000000 1000000000

Sample Output 5

1