Problem Statement

Takahashi works as a freelance programmer. He currently has N projects, each numbered from 1 to N.

Project i is expected to take D_i days until delivery, and upon completion of delivery, he will receive a reward of V_i yen.

Takahashi acquires projects through an agent company. Due to his contract with the agent company, he must pay P percent of the total received rewards to the agent company as a commission fee.

Takahashi is trying to calculate his income and expenses for the next M days. Find the amount obtained by subtracting the agent company's commission fee from the total rewards of projects whose delivery is completed within M days.

Note that the answer should be output as an integer with the decimal part truncated (rounded down).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^9
• 0 \leq P \leq 100
• 1 \leq D_i \leq 10^9
• 1 \leq V_i \leq 10^6
• All inputs are integers

Sample Input 1

4 5 10
3 1000
5 2000
6 3000
1 500

Sample Output 1

3150

Sample Input 2

3 2 20
3 100
5 200
10 300

Sample Output 2

0

Sample Input 3

10 30 15
10 12000
30 25000
31 40000
5 8000
25 15000
60 50000
1 3000
29 22000
45 18000
30 7000

Sample Output 3

78200

Sample Input 4

30 500 37
120 450000
800 320000
499 100000
500 999999
501 250000
30 75000
365 640000
1000 120000
250 333333
490 222222
10 1000000
700 111111
450 555555
600 444444
1 123456
499 654321
502 98765
300 777777
200 888888
550 99999
400 135790
480 246800
90 112233
510 445566
20 778899
470 314159
900 271828
350 161803
500 424242
750 202020

Sample Output 4

5666520

Sample Input 5

1 1000000000 100
1000000000 1000000

Sample Output 5

0

Problem Statement

At Takahashi's school, a fundraising activity was held during the school festival, and N teams collected donations. Team i collected A_i yen.

According to the school regulations, a group of teams is eligible for an award if the sum of their donations is at least half of the total amount collected by all teams. Takahashi wants to satisfy this condition with as few teams as possible.

Specifically, he wants to select a subset of the N teams such that the sum of the donations of the selected teams is at least half of the total amount collected by all teams (i.e., at least \lceil T / 2 \rceil, where T is the total amount). Find the minimum number of teams that need to be selected, and print this minimum count.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5
10 20 30 40 50

Sample Output 1

2

Sample Input 2

4
5 5 5 5

Sample Output 2

2

Sample Input 3

12
8 15 3 22 7 14 30 6 11 25 9 18

Sample Output 3

4

Sample Input 4

30
120 45 300 75 210 90 15 480 60 135 255 195 30 405 150 225 345 105 270 390 165 510 240 315 435 180 360 285 555 600

Sample Output 4

9

Sample Input 5

1
1000000000

Sample Output 5

1

Problem Statement

Takahashi is an epidemiological researcher investigating the spread of an infectious disease.

A certain region has N residents, each numbered from 1 to N. There are M recorded contact relationships between residents, and these contact relationships are bidirectional. That is, if resident A and resident B are in contact, infection can potentially spread from A to B and from B to A.

Takahashi wants to investigate the range to which infection can potentially spread from resident S, the initial infected person, through contact relationships.

The shortest contact count from resident S to resident T is defined as the minimum number of contact relationships traversed to reach resident T from resident S by following contact relationships. The shortest contact count from resident S to themselves is 0. If resident T cannot be reached from resident S by following any sequence of contact relationships, the shortest contact count to resident T is considered undefined.

For Takahashi, find the number of residents for whom the shortest contact count from resident S is defined and is at most K.

For example, if K = 0, only resident S themselves is counted, so the answer is 1. If K = 1, resident S and all residents in direct contact with S are counted. If K = 2, the contacts of those contacts are also included.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min(2 \times 10^5, \frac{N(N-1)}{2})
• 1 \leq S \leq N
• 0 \leq K \leq N
• 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
• (U_i, V_i) \neq (U_j, V_j) (i \neq j) (the same contact relationship is not recorded more than once)
• All inputs are integers

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

5

Sample Input 3

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

Sample Output 3

8

Problem Statement

There is a corridor consisting of an infinite row of cells labeled with integer coordinates. Only two people are in this corridor: Takahashi and Aoki, each standing on a different cell. Initially, Takahashi is on cell A and Aoki is on cell B.

The goal is to move Takahashi to cell C and Aoki to cell D.

You can perform the following operation any number of times (possibly zero):

• Choose any integer x, and swap the people on cell x and cell x + 1. Specifically, if both cells x and x+1 have a person, the two people exchange positions; if only one of the cells has a person, that person moves to the other cell; if neither cell has a person, nothing happens.

Since this operation is a swap between two adjacent cells, it is never possible for two people to occupy the same cell simultaneously.

It can be proven that the goal configuration is always achievable for the given inputs. Find the minimum number of operations required to achieve the goal configuration.

Constraints

• -10^{18} \leq A, B, C, D \leq 10^{18}
• A \neq B
• C \neq D
• All inputs are integers
• Under these constraints, the answer fits in a signed 64-bit integer type

Sample Input 1

0 2 1 3

Sample Output 1

2

Sample Input 2

0 1 1 0

Sample Output 2

1

Sample Input 3

-10 20 15 -5

Sample Output 3

49

Sample Input 4

-1000000000 2000000000 3000000000 -4000000000

Sample Output 4

9999999999

Sample Input 5

-1000000000000000000 1000000000000000000 999999999999999999 -999999999999999999

Sample Output 5

3999999999999999997

Problem Statement

Takahashi manages a piece of land consisting of N plots. The height of the i-th plot is H_i.

To level this land, Takahashi can repeatedly perform the following operation:

Operation: Choose a pair of integers (l, r) satisfying 1 \le l \le r \le N, and decrease the height of each plot from the l-th to the r-th plot by 1.

This operation can be performed zero or more times, and he can freely choose (l, r) each time (the same pair can be chosen multiple times). Note that this operation can only decrease heights; it cannot increase them.

Furthermore, at all points in time, including during the process and in the final state, the height of every plot must be at least 0.

Takahashi's goal is to make the sequence of heights "mountain-shaped" after all operations are completed. Letting H'_i be the height of the i-th plot after the operations, the sequence H'_1, H'_2, \ldots, H'_N is said to be mountain-shaped if there exists an index k (1 \le k \le N) such that:

H'_1 \le H'_2 \le \cdots \le H'_k \ge H'_{k+1} \ge \cdots \ge H'_N

That is, there exists some k such that the sequence from H'_1 to H'_k is monotonically non-decreasing, and the sequence from H'_k to H'_N is monotonically non-increasing. In particular, a monotonically non-decreasing sequence (the case where k = N), a monotonically non-increasing sequence (the case where k = 1), and a sequence where all heights are equal are also considered mountain-shaped. Additionally, when N = 1, the sequence is always mountain-shaped.

Takahashi wants to make the land mountain-shaped while minimizing the number of operations. Find the minimum number of operations required.

Constraints

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

Sample Input 1

5
2 1 3 2 1

Sample Output 1

1

Sample Input 2

6
0 2 2 5 3 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

21

Sample Input 4

50
12 0 15 15 3 22 7 30 18 5 5 40 1 26 26 9 33 14 14 2 45 11 29 6 6 38 20 4 31 31 8 17 23 23 10 36 13 27 0 19 19 34 16 16 28 21 21 35 24 12

Sample Output 4

343

Sample Input 5

1
1000000000

Sample Output 5

0