Problem Statement

Takahashi is developing a tax calculation system for a certain country.

In this country, the tax amount on income is calculated according to the following rules:

• A tax rate of P % is applied to the first L yen of income
• A tax rate of Q % is applied to the portion of income exceeding L yen

Note that P \leq Q does not necessarily hold.

Specifically, the tax amount T for a person with income S yen is calculated as follows:

• When S \leq L: T = \left\lfloor \dfrac{S \times P}{100} \right\rfloor
• When S > L: T = \left\lfloor \dfrac{L \times P + (S - L) \times Q}{100} \right\rfloor

Here, \lfloor x \rfloor denotes the largest integer not exceeding x (the floor function).

When S > L, note that the floor operation is applied only once to the result of dividing the sum L \times P + (S - L) \times Q by 100, rather than applying it individually to the L \times P part and the (S-L) \times Q part separately.

For example, when L = 100, P = 10, Q = 23, the tax amount for a person with income 150 yen is calculated as follows:

T = \left\lfloor \frac{100 \times 10 + (150 - 100) \times 23}{100} \right\rfloor = \left\lfloor \frac{1000 + 1150}{100} \right\rfloor = \left\lfloor \frac{2150}{100} \right\rfloor = \lfloor 21.5 \rfloor = 21 \text{ yen}

In this example, the result happens to be the same as when flooring each term individually (\lfloor 10 \rfloor + \lfloor 11.5 \rfloor = 10 + 11 = 21 yen), but in general they may differ.

Given the income S_i of each of N taxpayers, find each person's tax amount T_i.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq L \leq 10^9
• 0 \leq P \leq 100
• 0 \leq Q \leq 100
• 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 100 10 23
50
100
150

Sample Output 1

5
10
21

Sample Input 2

4 200 30 10
100
200
300
1

Sample Output 2

30
60
70
0

Sample Input 3

5 5000 15 40
0
3000
5000
8000
12345

Sample Output 3

0
450
750
1950
3688

Sample Input 4

8 1000000000 5 99
0
1
999999999
1000000000
1000000000
999999997
500000000
123456789

Sample Output 4

0
0
49999999
50000000
50000000
49999999
25000000
6172839

Sample Input 5

6 1 0 0
0
1
1000000000
0
0
1

Sample Output 5

0
0
0
0
0
0

Problem Statement

Takahashi is conducting a cell cultivation experiment in a biology laboratory.

At the start of the experiment, there are S cells in the culture dish. These cells have a special property: when Takahashi performs one "mitosis promotion" operation, all cells divide simultaneously, and the number of cells exactly doubles.

The only means Takahashi has to change the number of cells is this "mitosis promotion" operation, and due to the nutrient limitations of the culture dish, this operation can only be performed between 0 and K times, inclusive.

Takahashi's experimental goal is to make the number of cells exactly T.

Determine whether it is possible to change the number of cells from the initial S to exactly T. If it is possible, find the minimum number of "mitosis promotion" operations required.

Constraints

• 1 \leq S \leq 10^{18}
• 1 \leq T \leq 10^{18}
• 0 \leq K \leq 100
• All inputs are integers

Sample Input 1

3 24 5

Sample Output 1

3

Sample Input 2

7 100 10

Sample Output 2

-1

Sample Input 3

1000000000000 8000000000000 3

Sample Output 3

3

Problem Statement

Takahashi has a sequence of N positive integers. The i-th element (1 \leq i \leq N) of this sequence is A_i.

Takahashi is interested in the sum of contiguous subarrays of this sequence. Specifically, for a pair of integers (l, r) (1 \leq l \leq r \leq N), he considers the sum of elements from the l-th to the r-th:

A_l + A_{l+1} + \cdots + A_r

Given an integer K, find the number of pairs (l, r) such that this sum is at most K.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{14}
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

5 5
1 2 3 4 5

Sample Output 1

7

Sample Input 2

7 10
3 1 4 1 5 9 2

Sample Output 2

15

Sample Input 3

10 1000000000000
500000000 400000000 300000000 200000000 100000000 600000000 700000000 800000000 900000000 1000000000

Sample Output 3

55

Problem Statement

Takahashi is choosing souvenirs at his travel destination.

The souvenir shop sells N types of sweets and M types of drinks. The deliciousness of the i-th sweet is A_i, and the deliciousness of the j-th drink is B_j.

The satisfaction of combining the i-th sweet and the j-th drink is defined as the product of their deliciousness values, A_i \times B_j.

There are N \times M possible combinations of sweets and drinks in total. When these N \times M combinations are sorted in descending order of satisfaction, find the sum of the first K satisfaction values.

Note that combinations (i_1, j_1) and (i_2, j_2) are considered different as long as i_1 \neq i_2 or j_1 \neq j_2, even if their satisfaction values are equal. That is, when selecting the top K and computing the sum, each combination is counted individually as a separate one.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq \min(N \times M,\, 2 \times 10^5)
• 1 \leq A_i \leq 10^5 (1 \leq i \leq N)
• 1 \leq B_j \leq 10^5 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

2 3 3
3 1
2 4 1

Sample Output 1

22

Sample Input 2

4 4 5
5 3 7 1
4 6 2 8

Sample Output 2

196

Sample Input 3

5 6 8
10 20 30 40 50
3 6 9 12 15 18

Sample Output 3

5040

Problem Statement

Takahashi is a delivery person who needs to deliver packages to N houses. The houses are numbered 1, 2, \ldots, N, and the elevation of house i is V_i. Elevations are not necessarily distinct; different houses may have the same elevation.

Takahashi starts at house 1. The delivery to house 1 is already complete, and house 1 is already marked as visited. Takahashi must now deliver packages to all remaining houses 2, 3, \ldots, N.

Deliveries are performed as follows. Takahashi makes N - 1 moves. In each move, he selects exactly one unvisited house from his current location, moves to it, and marks it as visited. The destination does not need to be an adjacent house; he can move directly to any unvisited house. The delivery is complete once all houses have been visited exactly once. It does not matter which house he ends at (he does not need to return to house 1).

The cost of moving directly from house i to house j is determined by the following formula, regardless of what houses lie in between:

|V_i - V_j| \times |i - j|

In other words, the cost is the product of the absolute difference in elevations and the absolute difference in house numbers.

Minimize the total cost of the N - 1 moves.

Constraints

• 1 \leq N \leq 20
• 0 \leq V_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3
10 20 40

Sample Output 1

30

Sample Input 2

4
5 3 8 1

Sample Output 2

13

Sample Input 3

8
100 250 120 400 50 300 180 90

Sample Output 3

950

Sample Input 4

15
1000000000 0 500000000 250000000 750000000 125000000 875000000 62500000 937500000 31250000 968750000 15625000 984375000 7812500 992187500

Sample Output 4

1921875000

Sample Input 5

1
0

Sample Output 5

0