Problem Statement

Takahashi is the leader of a bomb disposal squad. Currently, N buildings are lined up in a row, numbered 1, 2, \ldots, N from left to right. Each building i has a durability value H_i.

Unfortunately, M explosions will occur in this area. The j-th explosion occurs centered at building T_j with power D_j. Note that the same building may be the center of multiple explosions.

When the j-th explosion occurs, the following durability reductions take place:

• The durability of building T_j decreases by D_j.
• If T_j \geq 2, the durability of building T_j - 1 decreases by \lfloor D_j / 2 \rfloor.
• If T_j \leq N - 1, the durability of building T_j + 1 decreases by \lfloor D_j / 2 \rfloor.

Here, \lfloor D_j / 2 \rfloor denotes the value obtained by dividing D_j by 2 and rounding down. Each explosion affects at most 3 buildings — the center building and its two neighbors — and does not affect buildings farther away.

The damage from each explosion is determined as described above regardless of the building's current durability, so the order in which the M explosions occur does not affect the result.

Durability values can become less than 0 (negative values). Even if a building's durability drops to 0 or below, it is not removed from the row and continues to be affected by subsequent explosions as usual (its durability may decrease further). Also, if such a building becomes the center of an explosion, it affects surrounding buildings as usual.

After all M explosions have finished, find the number of buildings whose final durability is 1 or greater.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq T_j \leq N (1 \leq j \leq M)
• 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers

Sample Input 1

5 2
10 20 30 20 10
3 15
1 8

Sample Output 1

5

Sample Input 2

7 4
100 50 80 120 60 40 90
2 60
5 100
2 30
7 50

Sample Output 2

4

Sample Input 3

10 6
500 300 450 200 600 150 400 250 350 100
3 400
7 300
1 600
5 500
10 200
4 100

Sample Output 3

4

Problem Statement

Takahashi is the quality control manager of a factory. The factory has a system where manufactured products are periodically inspected for quality, and products that do not meet the standards are disposed of.

The factory currently has N products, each numbered from 1 to N. The quality score of product i is A_i.

Takahashi performs Q quality inspections in order. In the j-th inspection (1 \leq j \leq Q), a threshold value T_j is set, and among the products that have not yet been disposed of at that point, all products whose quality score is strictly less than T_j are disposed of. Once a product is disposed of, it is no longer subject to subsequent inspections. Note that the threshold value T_j is determined independently for each inspection, so it may be smaller than the previous threshold. In that case, if the relevant products have already been disposed of in previous inspections, no new products are disposed of.

Immediately after each inspection, the number of products newly disposed of in that inspection is recorded. For all Q quality inspections, determine the number of products newly disposed of in each inspection.

Constraints

• 1 \leq N \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)
• 1 \leq T_j \leq 10^9 (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

5 3
3 1 4 1 5
2
4
3

Sample Output 1

2
1
0

Sample Input 2

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

Sample Output 2

3
0
2
0
2

Sample Input 3

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

Sample Output 3

4
5
0
3
0
3

Problem Statement

There are N rooms arranged in a row, numbered Room 1, Room 2, \ldots, Room N from left to right. Takahashi visits these rooms one by one in order from Room 1 to Room N, and for each room, he chooses to either "accept" or "decline" the job offered there. Each room has exactly one job, and he visits each room exactly once.

Each room i has a job with type T_i and reward A_i. There are two types of jobs:

• Loading job (T_i = 1): If accepted, he receives reward A_i and picks up one piece of luggage. The number of pieces of luggage he is carrying increases by 1.
• Unloading job (T_i = 0): If accepted, he receives reward A_i. If he is carrying one or more pieces of luggage, he puts down one piece, and the number of pieces of luggage he is carrying decreases by 1. If he is carrying no luggage, there is nothing to put down, so the number of pieces of luggage remains 0 (he still receives the reward).

The number of pieces of luggage Takahashi is carrying is initially 0. Throughout the process of accepting and declining jobs, the number of pieces of luggage must not exceed K at any point. This is because carrying too much luggage would be unmanageable.

Additionally, the number of pieces of luggage must be exactly 0 after visiting all rooms (because he cannot go home while still carrying luggage).

Determine the maximum total reward of the jobs Takahashi accepts while satisfying these conditions. Note that it is possible to accept no jobs at all, in which case the total reward is 0.

Constraints

• 1 \leq K \leq N \leq 10^5
• N K \leq 10^7
• T_i \in \{0, 1\}
• 1 \leq A_i \leq 10^6
• All input values are integers.

Sample Input 1

4 1
1 5
0 4
1 3
0 10

Sample Output 1

22

Sample Input 2

3 2
1 5
1 6
1 7

Sample Output 2

0

Sample Input 3

10 2
0 6
1 4
1 7
0 5
1 9
1 8
0 3
0 10
1 2
0 11

Sample Output 3

61

Sample Input 4

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

Sample Output 4

164

Sample Input 5

1 1
0 1000000

Sample Output 5

1000000

Problem Statement

Takahashi is the network administrator of a data center with N servers. The servers are numbered from 1 to N.

There are M available cables for connecting servers, and the cables are also numbered from 1 to M. The i-th cable (1 \leq i \leq M) bidirectionally connects server U_i and server V_i, with an installation cost of W_i. Each cable connects two distinct servers (i.e., U_i \neq V_i). However, there may be multiple cables connecting the same pair of servers.

Takahashi wants to select some cables to build a network so that all N servers can communicate with each other. The set of selected cables must form a spanning tree. A spanning tree is a graph that includes all N servers as vertices, where all servers are connected by the selected cables, and no cycles exist (in this case, exactly N-1 cables are selected).

However, due to security requirements, a specific set of K cables (numbered E_1, E_2, \dots, E_K) have already been contracted as dedicated encrypted communication lines and must be included in the network.

If a spanning tree exists that contains all K specified cables, output the minimum total installation cost of the N-1 cables included in that spanning tree. If no such spanning tree exists, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N - 1
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• 1 \leq W_i \leq 10^9
• 1 \leq E_j \leq M (1 \leq j \leq K)
• All E_j are distinct
• All input values are integers

Sample Input 1

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

Sample Output 1

8

Sample Input 2

3 3 2
1 2 1
1 2 2
2 3 3
1 2

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

29

Sample Input 4

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

Sample Output 4

77

Sample Input 5

2 1 0
1 2 1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is playing a paint game on a grid canvas with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is called cell (i, j).

Cell (i, j) has a score A_{i,j} assigned to it. Initially, no cells are painted.

Takahashi will drop paint onto the canvas Q times.

In the t-th paint drop, all cells on the canvas whose Manhattan distance from cell (R_t, C_t) is at most D_t are painted.

In other words, among all cells (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, all cells satisfying

|i - R_t| + |j - C_t| \leq D_t

are painted.

When a cell that has not yet been painted becomes newly painted, Takahashi earns the score of that cell. No score is earned when paint reaches a cell that is already painted.

For each paint drop, find the total score newly earned by Takahashi from that paint drop.

Constraints

• 1 \leq H \leq 2 \times 10^5
• 1 \leq W \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• H \times W \leq 4 \times 10^6
• H \times Q \leq 4 \times 10^6
• H + Q \leq 2 \times 10^5
• 0 \leq A_{i,j} \leq 10^9
• 1 \leq R_t \leq H
• 1 \leq C_t \leq W
• 0 \leq D_t \leq H + W
• All input values are integers

Sample Input 1

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

Sample Output 1

30
4
21
23

Sample Input 2

2 5
0 5 0 7 1
3 0 4 0 2
5
1 1 0
1 3 1
2 5 3
2 2 0
1 5 0

Sample Output 2

0
16
3
0
0

Sample Input 3

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

Sample Output 3

52
30
13
46
6
18
0
0

Sample Input 4

8 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
12
4 5 3
1 10 2
8 1 4
3 7 0
6 6 5
2 2 1
7 9 3
1 1 18
8 10 0
5 3 2
4 10 6
8 5 8

Sample Output 4

875
96
885
0
1121
60
80
123
0
0
0
0

Sample Input 5

1 1
1000000000
4
1 1 0
1 1 1
1 1 2
1 1 0

Sample Output 5

1000000000
0
0
0