Problem Statement

Takahashi manages an observation system consisting of N sensors arranged in a row. Each sensor is numbered from 1 to N, and the normal measurement value of the i-th sensor is A_i.

One day, due to an equipment malfunction, K sensors broke down and their measurement values could no longer be correctly obtained. The numbers of the broken sensors are B_1, B_2, \ldots, B_K. These are not necessarily in ascending order.

To fill in the data for the broken sensors, Aoki entered an estimated value for each broken sensor. The estimated value that Aoki entered for broken sensor B_j is C_j.

Let V_i denote the value of the i-th sensor after the data completion. V_i is determined as follows:

• If sensor i is not broken (i.e., i is not equal to any of B_1, B_2, \ldots, B_K), then V_i = A_i.
• If sensor i is broken (i.e., there exists a j such that i = B_j), then V_i = C_j.

To evaluate the smoothness of the entire system's data, Takahashi decided to calculate the "total variation," which is the sum of absolute differences between values of adjacent sensors. The total variation is defined as

\sum_{i=1}^{N-1} |V_{i+1} - V_i|

Find the total variation.

Note that while the normal measurement values A_1, A_2, \ldots, A_N of all sensors are given in the input, the estimated values are used instead of the normal measurement values for broken sensors.

Constraints

• 2 \leq N \leq 200000
• 1 \leq K \leq N
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_j \leq N (1 \leq j \leq K)
• B_1, B_2, \ldots, B_K are all distinct
• 1 \leq C_j \leq 10^9 (1 \leq j \leq K)
• All input values are integers

Sample Input 1

5 2
10 20 30 40 50
2 4
25 35

Sample Output 1

40

Sample Input 2

4 1
100 200 300 400
3
500

Sample Output 2

500

Sample Input 3

10 3
5 12 8 20 15 3 18 7 25 10
3 7 10
10 20 6

Sample Output 3

103

Sample Input 4

15 5
1000000000 500000000 300000000 700000000 100000000 900000000 200000000 800000000 400000000 600000000 150000000 850000000 50000000 950000000 250000000
5 2 11 8 14
999999999 1 777777777 123456789 987654321

Sample Output 4

6078395060

Sample Input 5

2 2
1 1000000000
2 1
500000000 500000000

Sample Output 5

0

Problem Statement

In the town where Takahashi lives, there is a single main street running from east to west. This main street can be regarded as a number line, where the west side corresponds to the direction of smaller coordinates and the east side corresponds to the direction of larger coordinates.

There are N houses built along this main street, numbered house 1, house 2, \ldots, house N from west to east. House i is located at coordinate X_i, and no two houses are built at the same position (X_1 < X_2 < \cdots < X_N).

There are also M shelters set up along this main street, numbered shelter 1, shelter 2, \ldots, shelter M from west to east. Shelter j is located at coordinate P_j, and no two shelters are set up at the same position (P_1 < P_2 < \cdots < P_M).

Note that a house and a shelter may be located at the same coordinate.

Takahashi, who is in charge of disaster prevention for the city, decided to determine the distance from each house to its nearest shelter so that residents of each house can evacuate to the nearest shelter in case of a disaster. Here, the distance from a point at coordinate a to a point at coordinate b is given by |a - b|.

For each house i (1 \leq i \leq N), find the distance from house i to the nearest shelter, that is, \displaystyle \min_{1 \leq j \leq M} |X_i - P_j|. Even if there are multiple nearest shelters, the distance is uniquely determined.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq P_j \leq 10^9 (1 \leq j \leq M)
• X_1 < X_2 < \cdots < X_N
• P_1 < P_2 < \cdots < P_M
• All inputs are integers

Sample Input 1

3 2
1 5 9
3 8

Sample Output 1

2
2
1

Sample Input 2

5 3
2 10 25 40 60
5 30 50

Sample Output 2

3
5
5
10
10

Sample Input 3

10 4
3 15 27 48 55 72 88 100 130 200
10 50 90 150

Sample Output 3

7
5
17
2
5
18
2
10
20
50

Problem Statement

Takahashi is a member of his school's gardening committee and is in charge of managing the flower bed.

The flower bed contains N plants arranged in a row, numbered Plant 1, Plant 2, \ldots, Plant N from the front. Each plant i (1 \leq i \leq N) has an initial moisture level of integer value A_i. Takahashi uses a watering can to water these plants.

Takahashi performs a total of M waterings. In the j-th watering (1 \leq j \leq M), he waters all plants in the contiguous range from Plant L_j to Plant R_j (inclusive), increasing the moisture level of each targeted plant by 1. If a plant is targeted by multiple waterings, its moisture level increases by the number of times it was targeted.

After all waterings are completed, find the number of plants whose moisture level is at least K.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
• All input values are integers

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

2

Sample Input 3

10 5 1000000000
999999999 0 999999998 500000000 0 1000000000 999999997 0 999999999 0
1 3
1 1
6 7
7 10
3 9

Sample Output 3

5

Problem Statement

A certain region has N bases, numbered from 1 to N. The bases are connected by M roads, where the i-th road bidirectionally connects base U_i and base V_i. Each road has a travel cost W_i, which is the same regardless of the direction of travel.

Takahashi works at the emergency medical center (base S) in this region. When a disaster occurs, medical supplies need to be delivered from the emergency medical center to each base.

Here, a path from base S to base v (v \neq S) is a sequence of bases S = p_0, p_1, \dots, p_k = v (k \geq 1) such that for each pair of consecutive bases (p_{j}, p_{j+1}) (0 \leq j \leq k-1), there exists a road connecting them. Note that the same base or the same road may be visited multiple times. The travel cost of this path is the sum of the travel costs of each road traversed along the path, that is, \displaystyle\sum_{j=0}^{k-1}(travel cost of the road connecting base p_j and base p_{j+1}).

For a base v (v \neq S), if there exists at least one path from base S to base v, then base v is said to be reachable from base S. Due to the structure of the road network, there may exist bases that are not reachable from base S.

Takahashi wants to deliver medical supplies to all bases reachable from base S with minimum travel cost. For each base v (v \neq S) reachable from base S, let d(v) denote the minimum travel cost among all paths from base S to base v.

Find the sum of d(v) over all bases v (v \neq S) reachable from base S. If there are no reachable bases other than base S, the sum is 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq S \leq N
• 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
• U_i \neq V_i (1 \leq i \leq M)
• 1 \leq W_i \leq 10^4 (1 \leq i \leq M)
• There is at most one road connecting the same pair of bases \{U_i, V_i\} (that is, if i \neq j then \{U_i, V_i\} \neq \{U_j, V_j\})
• All input values are integers

Sample Input 1

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

Sample Output 1

16

Sample Input 2

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

Sample Output 2

7

Sample Input 3

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

Sample Output 3

49

Sample Input 4

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

Sample Output 4

169

Sample Input 5

1 0 1

Sample Output 5

0

Problem Statement

Takahashi is a health official in a certain village. In this village, N residents live in a single row, numbered 1 to N from left to right.

Each resident i has an integer H_i representing their immunity. A resident whose immunity is 0 or less is in an infected state. Once a resident becomes infected, they remain infected.

The infection spreads in rounds. Initially, residents with H_i \leq 0 are infected, which we consider as the infected state at Round 0.

In Round 1, 2, \ldots, the following processes are performed in order:

• Every resident who is infected at the start of that round decreases the immunity of their adjacent residents (residents whose indices differ by exactly 1) by D each.
• If both the left and right neighbors of a resident are infected, that resident's immunity decreases by 2D in total.
• Residents whose immunity becomes 0 or less will newly become infected at the end of this round.
• If no residents newly become infected during this round, the spread terminates immediately, and no subsequent rounds are conducted.

Takahashi wants to find the number of residents who are infected when the spread ends.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq D \leq 10^9
• -10^9 \leq H_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

7 3
2 0 5 4 8 0 2

Sample Output 1

7

Sample Input 2

5 2
10 -1 10 10 10

Sample Output 2

1

Sample Input 3

15 6
18 11 -4 20 5 35 7 14 28 0 16 9 40 3 22

Sample Output 3

2

Sample Input 4

50 10
15 28 -3 45 12 80 5 70 35 -1 60 22 11 95 40 8 75 18 6 55 30 -20 90 4 14 100 65 25 9 85 13 7 120 50 -5 33 44 2 68 16 27 0 58 73 19 81 3 39 10 92

Sample Output 4

5

Sample Input 5

1 1000000000
1000000000

Sample Output 5

0