Problem Statement

Takahashi harvested N apples from an orchard. The weight of apple i (1 \leq i \leq N) is A_i grams.

After harvesting, Takahashi applied a coating agent to all the apples. Applying the coating agent increases each apple's weight by exactly R grams, so the weight of apple i after coating becomes A_i + R grams.

Takahashi wants to pack these apples into a gift box, so he wants all the apples to have the same weight. To achieve this, he decided to shave each apple to reduce its weight. Each apple can be shaved by any non-negative integer number of grams. However, the weight cannot be increased, and the weight after shaving cannot become less than 0 grams.

Takahashi's goal is to make all the apples have the same weight X grams (X is an integer satisfying 0 \leq X \leq \min(A_1+R, A_2+R, \ldots, A_N+R)). He wants to minimize the total amount shaved from all the apples, namely

\sum_{i=1}^{N} \bigl((A_i + R) - X\bigr)

Find the minimum value of this total.

Constraints

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

Sample Input 1

3 5
10 12 15

Sample Output 1

7

Sample Input 2

5 100
50 30 80 30 60

Sample Output 2

100

Sample Input 3

8 1000000000
500 1200 800 950 600 1100 750 900

Sample Output 3

2800

Problem Statement

Takahashi is about to enter university and is looking to purchase a new laptop.

Takahashi has found N candidate laptops. The i-th (1 \leq i \leq N) laptop has a price of P_i yen and a performance score of S_i. A higher performance score indicates better performance.

Takahashi's senior, Aoki, once bought a laptop choosing solely based on low price without considering performance, and regretted it because the performance was poor. Aoki advised Takahashi: "You should choose a laptop that has high performance relative to its price."

Following this advice, Takahashi defines the "cost performance" of the i-th laptop as \frac{S_i}{P_i}, and decides to choose the one with the maximum cost performance among the N laptops.

Find the number of the laptop with the maximum cost performance. If there are multiple laptops with the maximum cost performance, output the one with the smallest number.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq 10^6
• 1 \leq S_i \leq 10^6
• All inputs are integers

Sample Input 1

3
80000 400
100000 600
120000 480

Sample Output 1

2

Sample Input 2

5
50000 250
60000 360
80000 480
90000 450
70000 420

Sample Output 2

2

Sample Input 3

8
150000 600
200000 1000
180000 720
120000 600
250000 1000
100000 500
80000 320
160000 800

Sample Output 3

2

Problem Statement

Takahashi is exploring a dungeon represented as a grid with N rows and M columns. The cell at the i-th row from the top and the j-th column from the left is denoted as (i, j). Each cell (i, j) (1 \leq i \leq N, 1 \leq j \leq M) contains one gem with a value of A_{i,j}.

Takahashi is currently at the top-left cell (1, 1) of the dungeon. He wants to move to the bottom-right cell (N, M), which is the goal. In one move, Takahashi can advance exactly one cell to the right-adjacent cell or the down-adjacent cell from his current cell. That is, from cell (i, j), he can move to cell (i, j+1) (when j + 1 \leq M) or cell (i+1, j) (when i + 1 \leq N).

Takahashi collects the gems placed on all cells he passes through (including the starting cell (1, 1) and the ending cell (N, M)).

Takahashi wants to maximize the total value of the gems he collects. Among all paths from (1, 1) to (N, M), find and output the maximum possible total value of gems on the cells along the path.

Constraints

• 1 \leq N \leq 1000
• 1 \leq M \leq 1000
• 0 \leq A_{i,j} \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3
4 5 6
7 8 9

Sample Output 1

29

Sample Input 2

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

Sample Output 2

54

Sample Input 3

6 8
100 200 50 300 10 400 150 80
250 30 500 20 600 70 90 200
80 700 100 800 50 300 400 100
150 60 900 200 100 1000 50 350
300 400 50 150 200 80 600 700
100 200 300 400 500 600 700 800

Sample Output 3

5610

Problem Statement

Takahashi is in charge of audio for an event venue. The venue has a straight corridor, and N booths are lined up along the corridor. He needs to deliver announcement audio to each booth.

Positions along the corridor are represented by coordinates. Booth i is located at coordinate X_i, and the total sound volume required for the audio to be considered audible (hearing threshold) is D_i.

Takahashi will choose exactly one integer coordinate position P (any integer) on the corridor and place a speaker there. There is only one speaker placement location, and the position cannot be changed afterwards.

When the speaker is sounded once, its output volume is V. The volume that reaches booth i from a speaker placed at position P is \max(V - |X_i - P|, 0) per sounding. In other words, the volume attenuates as the distance between the speaker and the booth increases, and no sound reaches booths at a distance of V or more.

When the speaker is sounded K times (K is a positive integer) at the same position, the total volume reaching each booth i is K \times \max(V - |X_i - P|, 0). For booth i to be considered as having received the audio, this total must be at least the hearing threshold D_i.

To deliver audio to all booths, the above condition must be satisfied simultaneously for all booths i (1 \leq i \leq N). Therefore, if even one booth exists at a distance of V or more from the speaker position P, no amount of soundings can deliver volume to that booth, making it impossible to satisfy the condition.

Takahashi wants to minimize the number of times the speaker is sounded. Find the minimum number of times K the speaker must be sounded to deliver audio to all booths, when the speaker placement position P is chosen optimally.

However, if it is impossible to deliver audio to all booths regardless of which integer coordinate the speaker is placed at, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq V \leq 10^9
• 0 \leq X_i \leq 10^9
• 1 \leq D_i \leq 10^{18}
• All X_i are distinct
• All input values are integers

Sample Input 1

3 5
0 4
3 6
7 2

Sample Output 1

2

Sample Input 2

2 3
0 10
6 10

Sample Output 2

-1

Sample Input 3

8 10
100 15
102 80
105 21
108 100
111 70
113 42
116 18
118 55

Sample Output 3

55

Sample Input 4

30 100
5000 1000000000000
5006 123456789012
5012 987654321098
5018 555555555555
5024 314159265358
5030 271828182845
5036 777777777777
5042 888888888888
5048 999999999999
5054 111111111111
5060 222222222222
5066 333333333333
5072 444444444444
5078 666666666666
5084 135791357913
5090 246802468024
5096 101010101010
5102 909090909090
5108 123123123123
5114 456456456456
5120 789789789789
5126 100000000000
5132 200000000000
5138 300000000000
5144 400000000000
5150 500000000000
5156 600000000000
5162 700000000000
5168 800000000000
5174 900000000000

Sample Output 4

75000000000

Sample Input 5

1 1
1000000000 1000000000000000000

Sample Output 5

1000000000000000000

Problem Statement

Takahashi defined f(n) as the product of the digits of a positive integer n when written in standard decimal notation without leading zeros. For example, f(234) = 2 \times 3 \times 4 = 24 and f(5) = 5. If any digit is 0, then f(n) = 0. For example, f(102) = 1 \times 0 \times 2 = 0.

Takahashi wants to know the number of integers n between L and R (inclusive) that satisfy f(n) = K. Find this count.

Constraints

• 1 \leq L \leq R \leq 10^{18}
• 0 \leq K \leq 10^{18}
• L, R, K are integers

Sample Input 1

1 20 2

Sample Output 1

2

Sample Input 2

1 30 0

Sample Output 2

3

Sample Input 3

100 10000 36

Sample Output 3

93

Sample Input 4

123456789012 987654321098765432 720

Sample Output 4

32671066

Sample Input 5

1000000000000000000 1000000000000000000 0

Sample Output 5

1