Problem Statement

Takahashi aspires to become a mountaineer and is currently in training. The gym Takahashi attends has N members, and each member has a recorded maximum reachable altitude (hereafter simply called "altitude"). Takahashi is member number 1, and his current altitude is P meters. The altitude of member number i (2 \leq i \leq N) is S_i meters.

Takahashi wants to increase his altitude by learning from senior members who have a higher altitude than his. Specifically, Takahashi can repeat the following operation any number of times (including 0 times):

• Choose one member whose altitude is strictly greater than Takahashi's current altitude, and learn from that member. As a result of learning, Takahashi's altitude becomes equal to that member's altitude. However, each such operation costs C yen as a lesson fee.

Note that the altitudes of members other than Takahashi do not change through these operations.

Takahashi wants his final altitude to be at least T meters. If P \geq T already holds, no operations are needed. Find the minimum total lesson fee required to achieve the goal.

If it is impossible to achieve the goal no matter how the operations are performed, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P \leq 10^9
• 1 \leq T \leq 10^9
• 1 \leq C \leq 10^9
• 1 \leq S_i \leq 10^9 (2 \leq i \leq N)
• All input values are integers

Sample Input 1

5 100 500 1000
200 300 500 150

Sample Output 1

1000

Sample Input 2

4 1000 2000 500
800 900 950

Sample Output 2

-1

Sample Input 3

10 50 1000000000 100000
1000 5000 10000 100000 1000000 10000000 100000000 500000000 1000000000

Sample Output 3

100000

Problem Statement

Takahashi runs an orchard. The orchard has N apple trees lined up in a row, numbered tree 1, tree 2, \ldots, tree N from left to right. Tree i has H_i apples growing on it.

To streamline the harvesting process, Takahashi will choose one pair of integers (L, R) (1 \leq L \leq R \leq N) representing a range of consecutive tree numbers, and harvest apples from all trees from tree L to tree R. However, due to the limited number of workers, the number of trees in the range, R - L + 1, must be at most M, where M is the maximum number of trees that can be handled in a single harvesting operation.

Among the harvested apples, only apples from trees that meet the shipping standard can be shipped to market. Specifically, for tree i from tree L to tree R, only apples from trees satisfying H_i \geq K are eligible for shipping. From each eligible tree, all H_i apples growing on that tree are shipped. The total number of apples that can be shipped is the sum of H_i over all eligible trees. If there are no trees meeting the shipping standard within the range, the total number of apples that can be shipped is 0.

Find the maximum total number of apples that can be shipped when Takahashi chooses (L, R) optimally.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq N
• 1 \leq K \leq 10^9
• 0 \leq H_i \leq 10^9
• All input values are integers

Sample Input 1

5 3 5
3 7 2 8 6

Sample Output 1

15

Sample Input 2

4 2 10
3 5 2 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

20

Sample Input 4

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

Sample Output 4

47

Sample Input 5

1 1 1
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is a staff member at a meteorological observatory. Along a road extending in a straight line from east to west, there are N observation points, numbered 1, 2, \ldots, N in order, and he is surveying the snow accumulation status at each point.

Initially, the snowfall count at every point is 0.

This winter, there were a total of M snowfalls. In the i-th snowfall (1 \leq i \leq M), the snowfall count increased by 1 at every point from point L_i to point R_i (inclusive).

In other words, after all M snowfalls have finished, the snowfall count at each point equals the total number of times that point was included in the range of a snowfall.

His supervisor Aoki informed him that "points with a snowfall count of K or more require snow removal." To create a snow removal plan, Takahashi wants to determine the number of points whose snowfall count is K or more after all M snowfalls have finished.

Find the number of points whose snowfall count is K or more.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq M
• 1 \leq L_i \leq R_i \leq N
• All input values are integers.

Sample Input 1

10 3 2
1 5
3 7
6 10

Sample Output 1

5

Sample Input 2

5 3 3
1 2
3 4
4 5

Sample Output 2

0

Sample Input 3

100 5 3
10 50
20 60
30 70
40 80
50 90

Sample Output 3

41

Sample Input 4

1000000 4 2
1 500000
250001 750000
500001 1000000
1 1000000

Sample Output 4

1000000

Sample Input 5

1 1 1
1 1

Sample Output 5

1

Problem Statement

Takahashi works as a delivery driver for a courier service. For today's job, he needs to depart from the distribution center, stop by a specific relay point along the way, and deliver a package to the final destination.

Takahashi's assigned area contains N locations, each numbered from 1 to N. Location 1 is the distribution center, and location N is the final destination. There are M roads connecting locations, each of which is bidirectional and takes the same time to traverse in either direction. The i-th road (1 \leq i \leq M) connects location U_i and location V_i, and it takes C_i minutes to travel along this road.

For today's delivery, Takahashi needs to pick up another package at location K, which serves as a relay point, so he must pass through location K. Specifically, Takahashi travels from location 1 to location K, and then from location K to location N. During his travel, he may visit the same location multiple times and use the same road multiple times. Note that if K = 1, the distribution center also serves as the relay point, and if K = N, the final destination also serves as the relay point.

Find the minimum total travel time (in minutes) for Takahashi to travel from the distribution center (location 1) via the relay point (location K) to the final destination (location N). If at least one of the paths — from location 1 to location K or from location K to location N — does not exist, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i (no self-loops)
• 1 \leq C_i \leq 10^9
• There may be multiple roads connecting the same pair of locations
• All input values are integers
• When a solution exists, it is guaranteed that the answer is at most 2 \times 10^{14}

Sample Input 1

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

Sample Output 1

11

Sample Input 2

4 2 3
1 2 5
3 4 3

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

12

Problem Statement

Takahashi is analyzing weather data. He has temperature records for N days, where the temperature on day i (1 \leq i \leq N) is A_i degrees.

Takahashi wants to find periods during which the temperature was stable. When a pair of integers (l, r) satisfies 1 \leq l \leq r \leq N, the consecutive r - l + 1 days from day l to day r are called a "period." A period is said to be "stable" when the difference between the maximum and minimum temperatures within the period is at most K, that is, when

\max(A_l, A_{l+1}, \ldots, A_r) - \min(A_l, A_{l+1}, \ldots, A_r) \leq K

holds.

For a period of 1 day where l = r, the maximum and minimum values are equal, so the difference is 0. Under the constraints of this problem where K \geq 0, such a period is always stable. Therefore, there are at least N stable periods. Find the number of days in the longest stable period.

Constraints

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

Sample Input 1

7 3
20 22 21 23 19 25 24

Sample Output 1

4

Sample Input 2

10 5
15 18 12 14 16 20 19 17 22 25

Sample Output 2

4

Sample Input 3

15 10
-5 0 3 -2 5 8 2 -1 4 20 25 22 28 30 18

Sample Output 3

8