Problem Statement

Takahashi is keeping a household account book for N days.

Takahashi's account balance is initially 0 yen. On day i (1 \leq i \leq N), a transaction of A_i yen is recorded, where a positive value represents a deposit and a negative value represents a withdrawal. Each day's transaction is applied to the account balance in order (the account balance may become negative during the process). The account balance at the end of day N, after all transactions have been applied, is A_1 + A_2 + \cdots + A_N yen.

However, while reviewing the account book, Takahashi noticed that some transactions were recorded incorrectly. He then performs Q correction operations in order. In the j-th operation (1 \leq j \leq Q), he changes the transaction amount on day D_j to 0 yen. Once a day's transaction amount has been changed to 0, it remains 0 in all subsequent operations. In other words, with each operation, the number of days whose transaction amounts have been set to 0 increases.

After each operation, find the sum of all days' transaction amounts, that is, the account balance at the end of day N.

Note that D_1, D_2, \ldots, D_Q are all distinct. In other words, the same day's transaction amount is never changed more than once.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq N
• -10^9 \leq A_i \leq 10^9
• 1 \leq D_j \leq N
• D_1, D_2, \ldots, D_Q are all distinct
• All input values are integers

Sample Input 1

5 3
100 -50 200 -30 80
2
4
1

Sample Output 1

350
380
280

Sample Input 2

7 4
1000 -500 300 -200 400 -100 200
3
1
5
7

Sample Output 2

800
-200
-600
-800

Sample Input 3

10 5
1000000000 -999999999 500000000 -400000000 300000000 -200000000 100000000 -50000000 25000000 -12500000
1
3
5
7
9

Sample Output 3

-737499999
-1237499999
-1537499999
-1637499999
-1662499999

Problem Statement

Takahashi has N pipes. The length of the i-th pipe is A_i.

Some pipes are rusted. If the i-th pipe is rusted, B_i = 1; if it is not rusted, B_i = 0. Due to rust, the effective usable length of a rusted pipe is reduced to \max(A_i - C, 0). The effective length of a non-rusted pipe is A_i.

Takahashi freely selects at least 1 and at most N of these N pipes (each pipe can be selected at most once) and connects them in a line to form a single pipe. If only one pipe is selected, its effective length directly becomes the length of the finished pipe. If two or more pipes are selected, joint parts are used to connect the pipes, so the finished pipe's length is reduced by K for each connection point.

If the number of selected pipes is M, there are M - 1 connection points, so the length of the finished pipe is given by the following formula:

(\text{sum of effective lengths of the } M \text{ selected pipes}) - (M - 1) \times K

Takahashi wants the length of the finished pipe to be at least D. When the combination and number of pipes are chosen optimally, find the maximum possible length of the finished pipe. If the maximum value is at least D, output that value; if it is impossible to achieve a length of D or more regardless of the selection, output -1.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq D \leq 10^{14}
• 1 \leq K \leq 10^9
• 1 \leq C \leq 10^9
• 1 \leq A_i \leq 10^9
• B_i \in \{0, 1\}
• All input values are integers.

Sample Input 1

4 15 3 4
10 0
8 1
7 0
6 1

Sample Output 1

15

Sample Input 2

3 20 5 3
9 0
8 1
7 0

Sample Output 2

-1

Sample Input 3

8 40 4 5
12 0
11 1
20 0
9 1
15 0
7 0
14 1
10 0

Sample Output 3

55

Sample Input 4

15 90 7 10
30 0
25 1
18 0
40 1
12 1
9 0
27 0
14 1
33 0
21 1
16 0
45 1
8 1
19 0
24 1

Sample Output 4

180

Sample Input 5

1 1000000000 1000000000 1000000000
1000000000 0

Sample Output 5

1000000000

Problem Statement

In the town where Takahashi lives, there are N cherry blossom spots arranged in a straight line, numbered Spot 1, Spot 2, \ldots, Spot N in order. Adjacent spots are connected by promenades, and there exists promenade i (1 \leq i \leq N - 1) connecting Spot i and Spot i + 1. There are N - 1 promenades in total.

Each Spot j (1 \leq j \leq N) has a score P_j representing the beauty of the cherry blossoms at that location. Additionally, each promenade i (1 \leq i \leq N - 1) has a maintenance cost C_i.

Takahashi plans to maintain a contiguous interval of promenades to create a walking course. Specifically, he chooses integers l, r (1 \leq l \leq r \leq N - 1) and maintains all of promenade l, promenade l+1, \ldots, promenade r. By doing so, he can visit all of Spot l, Spot l+1, \ldots, Spot r+1 along the maintained promenades as his walking course.

The satisfaction obtained from the walking course is defined as the sum of the scores of the r - l + 2 spots included in the course:

P_l + P_{l+1} + \cdots + P_{r+1}

On the other hand, the total cost of maintenance is:

C_l + C_{l+1} + \cdots + C_r

Takahashi's budget is B, and he can only choose (l, r) such that the total cost is at most B. Takahashi must choose and maintain exactly one such interval.

Among all ways to choose (l, r) such that the total cost is at most B, find the maximum value of the satisfaction.

Note that, due to the constraints, the maintenance cost of each promenade is at most B, so l = r (maintaining just one promenade) always satisfies the condition, and there exists at least one valid choice of (l, r).

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq B \leq 10^{14}
• 1 \leq P_j \leq 10^9 (1 \leq j \leq N)
• 1 \leq C_i \leq B (1 \leq i \leq N - 1)
• All input values are integers

Sample Input 1

5 10
3 1 4 1 5
2 3 4 5

Sample Output 1

10

Sample Input 2

4 3
10 20 30 40
1 2 3

Sample Output 2

70

Sample Input 3

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

Sample Output 3

35

Sample Input 4

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

Sample Output 4

130

Sample Input 5

2 100000000000000
1000000000 1000000000
1

Sample Output 5

2000000000

Problem Statement

Takahashi lives in a country consisting of N cities. Each city is numbered from 1 to N, and the population of city i is M_i.

There are K roads in this country, and road k bidirectionally connects city U_k and city V_k. Takahashi can travel in either direction between two cities that are directly connected by a road. He may also pass through the same road or the same city multiple times.

Each time Takahashi travels from city a to an adjacent city b that is directly connected by a road, he must pay a toll of M_a \times M_b.

Takahashi is currently in city 1. There are P cities with airports in this country, which are cities E_1, E_2, \dots, E_P. Takahashi can leave the country once he reaches any city with an airport. If city 1 itself has an airport, he can leave without moving, and the total toll is 0.

Find the minimum total toll Takahashi must pay to travel from city 1 to any city with an airport. It is guaranteed that at least one city with an airport is reachable from city 1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• 1 \leq P \leq N
• 1 \leq M_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq U_k < V_k \leq N (1 \leq k \leq K)
• All pairs (U_k, V_k) are distinct
• 1 \leq E_p \leq N (1 \leq p \leq P)
• E_1, E_2, \dots, E_P are all distinct
• At least one city with an airport is reachable from city 1 via roads
• All input values are integers

Sample Input 1

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

Sample Output 1

7

Sample Input 2

3 2 1
5 3 7
1 2
2 3
1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

12

Sample Input 4

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

Sample Output 4

18

Sample Input 5

2 1 1
1 10000
1 2
2

Sample Output 5

10000

Problem Statement

Takahashi has been hired to paint a fence consisting of N boards. The boards are numbered from 1 to N, and initially all boards are unpainted.

Aoki gives Takahashi M painting instructions. The i-th instruction (1 \leq i \leq M) is "paint all boards from board L_i to board R_i (inclusive)." If a board is painted by multiple instructions, it ends up in the same state as if it were painted once.

Due to his limited stamina, Takahashi must ignore exactly K consecutive instructions out of the M instructions. Specifically, he chooses an integer s satisfying 1 \leq s \leq M - K + 1, ignores the K instructions from the s-th to the (s + K - 1)-th (not executing them), and executes all the remaining M - K instructions.

Takahashi wants to maximize the number of boards that are ultimately painted by optimally choosing the interval of instructions to ignore. Find the maximum number of boards that are ultimately painted.

Constraints

• 1 \leq N \leq 10^9
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq M
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
• All inputs are integers

Sample Input 1

10 4 2
1 3
4 6
2 5
8 10

Sample Output 1

7

Sample Input 2

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

Sample Output 2

8

Sample Input 3

50 10 3
1 10
5 15
20 25
12 22
30 40
35 45
2 8
18 19
41 50
10 30

Sample Output 3

50

Sample Input 4

1000000000 25 7
1 100000
50000 200000
150000 300000
250000 400000
350000 500000
450000 600000
550000 700000
650000 800000
750000 900000
850000 1000000
10000000 20000000
15000000 25000000
24000000 30000000
100000000 200000000
180000000 260000000
250000000 350000000
340000000 420000000
500000000 600000000
590000000 700000000
690000000 800000000
799999999 900000000
850000000 950000000
940000000 1000000000
123456789 123456789
400000000 500000000

Sample Output 4

920350003

Sample Input 5

1 1 1
1 1

Sample Output 5

0