Problem Statement

Takahashi manages a water system consisting of N tanks arranged in a horizontal row. The tanks are numbered from 1 to N from left to right, and tank i currently contains A_i liters of water.

To adjust the water levels in this system, Takahashi can perform the following operation any number of times (including zero times). The pair of tanks chosen can be different for each operation.

Operation: Choose two adjacent tanks i and i + 1 (1 \leq i \leq N - 1), and transfer 1 liter of water from one tank to the other. Specifically, perform one of the following:

• Decrease the water in tank i by 1 liter and increase the water in tank i + 1 by 1 liter.
• Decrease the water in tank i + 1 by 1 liter and increase the water in tank i by 1 liter.

However, the water level in each tank must remain 0 or more after every operation. That is, you cannot decrease the water in a tank that has 0 liters of water.

Note that this operation does not change the total amount of water.

Takahashi wants to make the water levels of all tanks equal by repeating operations. Determine whether this is achievable. If it is possible, output Yes; otherwise, output No.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq A_i \leq 10^9
• All input values are integers

Sample Input 1

3
1 2 3

Sample Output 1

Yes

Sample Input 2

4
1 2 3 5

Sample Output 2

No

Sample Input 3

6
0 1000000000 500000000 200000000 100000000 200000000

Sample Output 3

No

Problem Statement

Takahashi is climbing from the base of a mountain toward the summit.

The trail from the base to the summit is divided into N sections, each with a difficulty rating representing the severity of the climb. The difficulty of the i-th section (1 \leq i \leq N) is D_i.

Takahashi starts the climb with stamina S and passes through all sections in order from the 1-st to the N-th. Even if his stamina drops to 0 or below during the climb, he continues onward without stopping until the end.

Takahashi can be in either an "exhausted state" or a "non-exhausted state." He starts the climb in a non-exhausted state. Once he becomes exhausted, he remains exhausted for the rest of the climb, regardless of how much stamina he recovers afterward.

When passing through each section i (1 \leq i \leq N), the following steps are performed in this order:

• Stamina consumption: If Takahashi is in a non-exhausted state, his stamina decreases by D_i. If he is in an exhausted state, his stamina decreases by 2 \times D_i.
• Exhaustion check: If his stamina after consumption is 0 or below and he is currently in a non-exhausted state, Takahashi becomes exhausted. (If he is already exhausted, nothing happens.)
• Mountain hut recovery: If there is a mountain hut immediately after passing through section i, his stamina increases by the recovery amount of that hut. If there is no hut, nothing happens. There is no upper limit on stamina, and it can exceed the initial stamina.

There are several mountain huts along the trail. There are M huts (possibly 0), and the j-th hut (1 \leq j \leq M) is located immediately after passing through section P_j, providing a stamina recovery of R_j. Mountain huts can only exist immediately after sections 1 through N-1. There is no mountain hut immediately after section N (the last section).

Determine Takahashi's remaining stamina when he arrives at the summit after passing through all N sections.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq N - 1
• 1 \leq S \leq 10^9
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_j \leq N - 1 (1 \leq j \leq M)
• All P_j are distinct
• 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 1 10
3 4 2
2 3

Sample Output 1

4

Sample Input 2

3 0 5
3 4 2

Sample Output 2

-6

Sample Input 3

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

Sample Output 3

4

Sample Input 4

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

Sample Output 4

-38

Sample Input 5

1 0 1
1

Sample Output 5

0

Problem Statement

Takahashi has decided to organize the bookshelf in his room. The bookshelf contains N books, and the thickness of the i-th book (1 \leq i \leq N) is V_i. Two books with different indices may have the same thickness.

Takahashi wants to rearrange all N books into a single row in any order, using each book exactly once. Since a large difference in thickness between adjacent books looks unappealing, he wants to rearrange the books so that the sum of absolute differences of thicknesses between adjacent books is minimized.

Specifically, let A_k denote the thickness of the k-th book from the left after rearranging. Here, (A_1, A_2, \ldots, A_N) is a permutation of (V_1, V_2, \ldots, V_N). Find the minimum value of:

\sum_{k=1}^{N-1} |A_k - A_{k+1}|

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq V_i \leq 10^9
• All input values are integers.

Sample Input 1

4
3 1 4 2

Sample Output 1

3

Sample Input 2

7
10 50 30 20 40 5 25

Sample Output 2

45

Sample Input 3

10
1000000000 1 500000000 250000000 750000000 100 999999999 2 123456789 987654321

Sample Output 3

999999999

Problem Statement

Takahashi is trying to walk along a long corridor.

This corridor is represented as the closed interval [0, L] on a number line. Takahashi walks straight through the corridor from the start point at coordinate 0 to the goal point at coordinate L.

There are N Wi-Fi routers installed in the corridor. The i-th router (1 \leq i \leq N) is installed at coordinate X_i and transmits a signal to all points within distance R_i from it (including points at exactly distance R_i). That is, the coverage area of the i-th router is the closed interval [X_i - R_i, X_i + R_i]. Note that multiple routers may be installed at the same coordinate.

Since Takahashi is making an online call on his smartphone while moving, he needs to be connected to Wi-Fi at every point along the corridor.

Determine whether every coordinate in the closed interval [0, L] is covered by at least one of the N routers. If a router's coverage area extends beyond the closed interval [0, L], the portion outside the interval does not affect the determination. It is sufficient that the portion within the closed interval [0, L] is properly covered.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L \leq 10^9
• 0 \leq X_i \leq L
• 1 \leq R_i \leq 10^9
• All input values are integers

Sample Input 1

3 10
2 3
5 2
8 3

Sample Output 1

Yes

Sample Input 2

2 20
5 5
18 3

Sample Output 2

No

Sample Input 3

5 1000000000
100000000 150000000
300000000 100000000
500000000 150000000
700000000 150000000
900000000 150000000

Sample Output 3

Yes

Problem Statement

Takahashi, working as a librarian, has been assigned the task of shelving N books onto a bookshelf.

The bookshelf has M empty spaces arranged in a row, numbered from left to right as space 1, space 2, \ldots, space M. Each space j has an integer value C_j representing its "weight capacity," and each space can hold at most 1 book.

The books are numbered from 1 to N, and book i has an integer value W_i representing its "weight."

Takahashi determines the placement for each book one at a time, in the order book 1, book 2, \ldots, book N, using the following procedure:

• Among the spaces that do not yet have a book placed on them, consider as candidates those whose weight capacity is at least the weight of the book (i.e., C_j \geq W_i).
• If there is at least one candidate, place the book on the candidate space with the smallest number. The space where a book is placed becomes occupied and can no longer be selected for subsequent books.
• If there are no candidates, give up on shelving that book. A book that is given up on is not placed on the bookshelf and is never reconsidered.

After considering the placement for all books, determine the number of books that were successfully placed on the bookshelf.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
• All inputs are integers

Sample Input 1

4 5
3 5 2 7
4 6 3 8 2

Sample Output 1

4

Sample Input 2

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

Sample Output 2

5

Sample Input 3

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

Sample Output 3

8