Problem Statement

Takahashi works as a shipping manager at a warehouse.

This warehouse manages N types of products, and the initial stock quantity of product i (1 \leq i \leq N) is R_i units.

Today, M shipping requests arrive in order. The j-th (1 \leq j \leq M) shipping request asks to ship S_j units of product F_j.

Takahashi processes the requests in order from the 1-st to the M-th. For each request, he performs the following:

• If the current stock quantity of product F_j is at least S_j, the shipment succeeds, and the stock quantity of product F_j is decreased by S_j.
• If the current stock quantity of product F_j is less than S_j, the shipment fails, and the stock quantity does not change. Partial shipment (shipping only the available amount) is not performed. Additionally, failed requests are never reprocessed later.

After all shipping requests have been processed, determine the number of requests that were successfully shipped.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq R_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq F_j \leq N (1 \leq j \leq M)
• 1 \leq S_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

2 3
0 1
1 1
2 5
1 3

Sample Output 2

0

Sample Input 3

5 8
100 50 200 0 30
1 50
3 100
2 50
4 1
1 50
1 1
5 30
3 150

Sample Output 3

5

Sample Input 4

10 15
1000000000 500000000 0 100 999999999 1 1000000000 50 300 200
1 500000000
1 500000000
1 1
5 999999999
5 1
6 1
6 1
3 1
4 50
4 50
4 1
7 1000000000
8 25
8 25
10 200

Sample Output 4

10

Sample Input 5

1 1
0
1 1

Sample Output 5

0

Problem Statement

Takahashi is responsible for shoveling snow on the road in front of his house during winter.

The road is divided into N sections, numbered from left to right as section 1, section 2, \ldots, section N. The amount of snow accumulated in section i is A_i centimeters.

Takahashi uses a snow shovel to clear the snow. In one snow shoveling session, he chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and reduces the amount of snow in each of the consecutive sections from section l to section r by 1 centimeter. However, if at the time before the operation, any section among sections l, l+1, \ldots, r has 0 centimeters of snow, he cannot choose that pair (l, r). Snow shoveling can be performed any number of times, and he may choose a different pair (l, r) each time, or choose the same pair multiple times.

Find the minimum number of snow shoveling sessions required to make the amount of snow in all sections exactly 0 centimeters.

Constraints

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

Sample Input 1

3
3 1 2

Sample Output 1

4

Sample Input 2

5
2 3 2 1 4

Sample Output 2

6

Sample Input 3

8
5 0 3 0 8 2 0 1

Sample Output 3

17

Problem Statement

Takahashi is organizing a marathon with N participants. The players are numbered from 1 to N, and each player i (i = 1, 2, \ldots, N) has a "stamina value" L_i. The stamina values are a permutation of 1 through N, meaning they are distinct integers between 1 and N inclusive.

In the race, the N players line up in a single row from left to right at the start. Initially, player i is at the i-th position from the left. In other words, each player's number matches their initial position.

Once the race begins, players retire one by one in increasing order of their stamina values. That is, the player with stamina value 1 retires first, then the player with stamina value 2, and so on, until finally the player with stamina value N retires.

When a player retires, they leave the row. The remaining players maintain their relative order and close any gaps, forming a contiguous row from the left again.

As the record keeper, Takahashi wants to record, just before each player retires, what position from the left that player holds among the remaining players. Here, "just before retiring" means the player themselves is still in the row at that point.

For k = 1, 2, \ldots, N in order, determine the position from the left of the player with stamina value k among the remaining players (including themselves) just before that player retires.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq N
• L_1, L_2, \ldots, L_N is a permutation of 1 through N
• All input values are integers

Sample Input 1

5
3 1 4 5 2

Sample Output 1

2
4
1
1
1

Sample Input 2

4
4 3 2 1

Sample Output 2

4
3
2
1

Sample Input 3

10
5 3 8 1 10 2 7 9 4 6

Sample Output 3

4
5
2
6
1
5
3
1
2
1

Sample Input 4

20
12 5 18 3 14 9 20 1 16 7 11 19 6 2 17 10 4 15 8 13

Sample Output 4

8
13
4
14
2
10
7
12
4
9
6
1
8
2
6
3
4
1
2
1

Sample Input 5

1
1

Sample Output 5

1

Problem Statement

Takahashi is a quality inspector at a factory. He is inspecting N products lined up in a row on a belt conveyor.

The i-th product (1 \leq i \leq N) has a quality score A_i and a weight B_i.

Given a threshold value K, any product with a quality score less than K (A_i < K) is considered defective and must be returned. Products with a quality score of K or higher are considered good.

Defective products to be returned are packed into boxes for shipping. Each defective product must be placed in exactly one box, and boxes may only contain defective products. Empty boxes are not used. The number of boxes can be chosen freely, but each box must satisfy the following condition:

• The defective products placed in the same box must form a contiguous segment in the original arrangement. That is, if the positions of defective products placed in a box are l, l+1, \ldots, r (l \leq r), then all products from position l to r must be defective (no good products may exist in between).

The shipping cost of a single box is determined by the maximum weight among the defective products it contains. Specifically, the maximum value of B_i among the products in the box is the shipping cost of that box. The total shipping cost is the sum of the shipping costs of all boxes.

You are given Q threshold values K_1, K_2, \ldots, K_Q. For each K_j, find the minimum total shipping cost to return all defective products. If there are no defective products, the total shipping cost is 0.

Each query is independent (the arrangement of products is shared, but only the threshold value changes).

Constraints

• 1 \leq N
• 1 \leq Q
• N + Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• 1 \leq K_j \leq 10^9
• All input values are integers

Sample Input 1

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

Sample Output 1

0
17
10
10

Sample Input 2

4 5
3 8
3 2
1 5
4 6
1
2
3
4
5

Sample Output 2

0
5
5
8
8

Sample Input 3

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

Sample Output 3

0
48
63
56
20
27
41
56

Sample Input 4

30 10
100 30
20 5
80 100
40 7
60 50
10 80
90 20
30 60
70 10
50 90
25 55
75 35
15 75
85 15
35 65
95 25
45 85
55 45
5 95
65 40
12 70
88 22
42 82
78 32
18 72
58 52
98 12
28 62
68 42
38 92
1
11
31
51
71
91
101
46
66
86

Sample Output 4

0
175
574
940
656
287
100
905
778
459

Sample Input 5

1 1
1 1000000000
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi has created a management plan that cycles every N days. In this plan, the revenue, purchasing costs, and labor costs are determined for each day.

On day i (1 \leq i \leq N) of the management plan, at the end of that day, the funds increase by A_i - B_i - C_i yen, where A_i represents revenue, B_i represents purchasing costs, and C_i represents labor costs. (If the increase is negative, the funds decrease.)

This management plan returns to day 1 on the day after day N, and the same plan repeats infinitely.

If at the end of any day the funds become less than 0 yen (negative), the company is considered to have gone bankrupt.

Q queries are given. In the j-th query, Takahashi starts management from day L_j of the management plan, and his funds are S_j yen at the point before day L_j's processing occurs.

After that, management is conducted daily following the order of the management plan. That is, the days in the management plan proceed in the order L_j, L_j+1, \ldots, N, 1, 2, \ldots. The first day on which management is conducted (day L_j of the management plan) is counted as "day 1 since the start of management."

For each query, output on which day since the start of management the company goes bankrupt for the first time (at the end of that day). If the company never goes bankrupt no matter how long management continues, output 0.

Constraints

• 1 \leq N
• 1 \leq Q
• N + Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 0 \leq B_i \leq 10^9
• 0 \leq C_i \leq 10^9
• 1 \leq L_j \leq N
• 0 \leq S_j \leq 10^{12}
• All inputs are integers

Sample Input 1

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

Sample Output 1

2
14
1
3
22

Sample Input 2

4 4
5 2 3
10 4 1
0 0 0
7 3 2
1 0
2 1
3 100
4 5

Sample Output 2

0
0
0
0

Sample Input 3

8 8
100 30 20
20 50 10
0 40 30
80 20 20
10 5 5
50 60 20
200 100 50
30 20 40
1 0
2 25
3 100
4 10
5 60
6 5
7 1000
8 15

Sample Output 3

3
1
17
8
7
1
269
1

Sample Input 4

20 15
1000000000 400000000 300000000
200000000 500000000 100000000
0 600000000 500000000
750000000 250000000 250000000
123456789 123456789 0
900000000 100000000 100000000
10000000 20000000 30000000
500000000 600000000 100000000
1000000000 0 0
0 0 0
300000000 100000000 250000000
800000000 900000000 50000000
450000000 200000000 100000000
100000000 300000000 400000000
600000000 100000000 100000000
700000000 350000000 350000000
1 1000000000 0
999999999 1 1
250000000 250000000 250000000
400000000 100000000 200000000
1 0
1 1000000000000
3 500000000
5 123456789
7 10000000
9 0
10 100
12 800000000
14 1500000000
16 0
18 999999999999
20 300000000
4 700000000
11 250000000
15 50

Sample Output 4

2
0
1
19
1
9
2
6
10
2
0
4
0
4
3

Sample Input 5

1 5
0 1000000000 1000000000
1 0
1 1
1 1999999999
1 2000000000
1 1000000000000

Sample Output 5

1
1
1
2
501