Problem Statement

Takahashi is conducting a bacteria growth experiment in a biology laboratory.

In this experiment, bacteria colonies grow in a special culture medium. Each colony divides at regular intervals, and a new colony with exactly 2 times the size of the original colony is born.

At the start of the experiment, there is only 1 colony of size 1 in the culture medium. After that, the following growth occurs K times.

Growth: For each colony that currently exists, a new colony with twice the size of that colony is born. At this time, the original colony also remains.

In other words, the number of colonies increases each time growth occurs. However, there may be multiple colonies of the same size, but since the research records them classified by size, colonies of the same size are counted as 1 type.

After K growths have occurred, how many types of colonies exist in the culture medium? In other words, find the number of distinct values that appear as sizes of existing colonies.

Constraints

• 1 \leq K \leq 10^{18}
• K is an integer

Sample Input 1

2

Sample Output 1

3

Sample Input 2

10

Sample Output 2

11

Sample Input 3

1000000000000000000

Sample Output 3

1000000000000000001

Problem Statement

Takahashi is a school teacher who is tallying the results of the final exam.

In this exam, only students who scored at least L points and at most R points will pass. Students who scored too low will not pass, and students who scored too high are also suspected of cheating, so they will not pass either.

N students took this exam, and the i-th student scored P_i points.

Takahashi wants to know the student ID of the student with the highest score among those who passed.

Find the student ID of the student with the maximum score among the students who passed. If there are multiple such students, output the student ID of the one with the smallest student ID. However, if no students passed, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq L \leq R \leq 100
• 0 \leq P_i \leq 100 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 60 80
55 72 80 90 65

Sample Output 1

3

Sample Input 2

8 50 70
45 70 60 70 80 55 30 68

Sample Output 2

2

Sample Input 3

10 40 60
35 100 25 55 60 60 75 42 38 90

Sample Output 3

5

Problem Statement

Takahashi is about to go shopping on an online shopping site.

The shopping site has N items, and each item i has a price of D_i yen. Takahashi plans to purchase all the items.

Takahashi has a special discount coupon. By using this coupon, he can reduce the price of selected items to 0 yen. However, there is a restriction that the coupon can be applied to at most K items.

Takahashi wants to use the coupon optimally to minimize the total amount he pays. Find the minimum total amount he needs to pay when using the coupon optimally.

Constraints

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

Sample Input 1

5 2
100 250 300 150 200

Sample Output 1

450

Sample Input 2

7 3
500 1200 800 300 950 1100 450

Sample Output 2

2050

Sample Input 3

10 4
1000000000 999999999 500000000 750000000 250000000 800000000 600000000 400000000 350000000 900000000

Sample Output 3

2850000000

Problem Statement

Takahashi is a merchant doing business along a highway that extends from east to west. There are N towns lined up in a row along this highway, numbered 1, 2, ..., N from west to east. Doing business in the i-th town yields a profit of A_i, but costs B_i yen as accommodation expenses.

Takahashi has decided to select some of these towns to do business in. However, Takahashi's carriage has the following restriction:

• The towns visited do not need to have consecutive numbers, but when the visited town numbers are arranged in ascending order, the difference between any two adjacent numbers must be at most K. In other words, if the visited town numbers in ascending order are p_1, p_2, \ldots, p_m, then p_{j+1} - p_j \leq K must hold for all 1 \leq j \leq m - 1. This is because the carriage has a limit on the distance it can travel at once.

The total accommodation expenses Takahashi can prepare is M yen. When selecting towns such that the total accommodation expenses of visited towns is at most M yen, find the maximum possible total profit.

Note that if no town is visited, the total profit is 0.

Constraints

• 1 \leq N \leq 200
• 1 \leq M \leq 200
• 1 \leq K \leq N
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq M
• All inputs are integers

Sample Input 1

5 10 2
8 3
5 4
10 5
3 2
7 3

Sample Output 1

21

Sample Input 2

4 5 1
100 2
200 3
150 2
50 1

Sample Output 2

350

Sample Input 3

10 50 3
1000000000 10
500000000 8
800000000 12
300000000 5
600000000 15
900000000 20
400000000 7
700000000 11
200000000 6
550000000 9

Sample Output 3

3450000000

Problem Statement

Takahashi is analyzing weather data. There is a record of temperature observations taken over N consecutive days in a certain region, where the temperature on day i was H_i degrees.

Takahashi wants to select a consecutive period of K days from this observation data and investigate the temperature variation range during that period.

Here, the "temperature variation range" for a consecutive period of K days is defined as the difference between the maximum temperature and the minimum temperature during that period.

Takahashi wants to find a consecutive period of K days that maximizes the temperature variation range. Find the maximum value of the temperature variation range.

Constraints

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

Sample Input 1

5 3
2 5 1 8 4

Sample Output 1

7

Sample Input 2

7 4
-3 10 5 -2 8 1 6

Sample Output 2

13

Sample Input 3

12 5
100 -50 200 150 -100 300 50 -200 250 0 -150 400

Sample Output 3

600