Problem Statement

Takahashi is in charge of air conditioning management for an office building. Today, he needs to check the temperatures of N rooms in the building.

For a comfortable office environment, the temperature of each room must be kept at 37 degrees or below. Rooms with temperatures higher than 37 degrees must be cooled using air conditioners. Rooms whose temperatures are already 37 degrees or below do not need cooling.

The current temperature of the i-th room (1 \leq i \leq N) is T_i degrees. In one operation, Takahashi can choose one of the N rooms and lower its temperature by exactly 0.1 degrees. The same room can be chosen multiple times.

Find the minimum total number of operations required to make the temperature of every room 37 degrees or below.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0.0 \leq T_i \leq 50.0
• T_i is a real number with exactly one decimal place (i.e., 10 \times T_i is an integer)
• In the input, each T_i is always written with exactly one decimal place (e.g., even integer values are given as 37.0)

Sample Input 1

3
36.5 37.0 38.2

Sample Output 1

12

Sample Input 2

5
37.3 40.0 36.0 38.5 37.0

Sample Output 2

48

Sample Input 3

10
35.0 37.5 42.0 37.0 39.8 36.9 50.0 38.0 37.1 41.5

Sample Output 3

269

Problem Statement

Takahashi is a buyer for a department store. For an upcoming special sale, he needs to select products from the warehouse and display them on the sales floor.

There are N products in the warehouse, and the i-th product (1 \leq i \leq N) has a selling price of V_i. The warehouse is divided into M areas numbered from 1 to M, and the i-th product is stored in area C_i.

Some areas of the warehouse are inaccessible due to renovation work. There are Q accessible areas, and their area numbers are given as S_1, S_2, \ldots, S_Q. All other areas are inaccessible.

Takahashi will select at most K products (possibly 0) from those stored in accessible areas and display them on the sales floor. Each product can be selected at most once. Due to space limitations on the sales floor, no more than K products can be displayed.

Find the maximum possible total selling price of the products displayed on the sales floor. Note that if no products are displayed, the total selling price is 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^5
• 1 \leq K \leq N
• 1 \leq Q \leq M
• 1 \leq V_i \leq 10^9
• 1 \leq C_i \leq M
• 1 \leq S_j \leq M
• S_1, S_2, \ldots, S_Q are all distinct
• All inputs are integers

Sample Input 1

5 3 2 2
100 1
200 2
150 1
300 3
50 2
1 2

Sample Output 1

350

Sample Input 2

8 5 4 3
500 1
300 2
800 3
150 4
600 2
250 5
400 1
100 3
2 3 5

Sample Output 2

1950

Sample Input 3

12 6 5 4
1000000000 1
999999999 2
888888888 3
777777777 4
666666666 5
555555555 6
444444444 1
333333333 2
222222222 3
111111111 4
100000000 5
50000000 6
1 2 4 6

Sample Output 3

3777777775

Problem Statement

Takahashi and Aoki are each responsible for managing street lights on different roads.

Each road has multiple street lights. For each street light, exactly one lighting operation is performed at an integer time. A street light whose lighting operation is performed at integer time t is lit at the D integer times t, t+1, \ldots, t + D - 1.

The brightness of a road at a given integer time is the number of street lights that are lit on that road at that time. If multiple street lights are lit at the same time, each one is counted separately.

Takahashi performed a lighting operation exactly once for each of the N street lights on his road. The lighting operation for the i-th (1 \leq i \leq N) street light was performed at time A_i.

Aoki performed a lighting operation exactly once for each of the M street lights on his road. The lighting operation for the j-th (1 \leq j \leq M) street light was performed at time B_j.

Note that multiple different street lights on the same road may have their lighting operations performed at the same time. Also, A_1, A_2, \ldots, A_N and B_1, B_2, \ldots, B_M are not necessarily given in ascending order.

At a given integer time, if the brightness of Takahashi's road is strictly greater than the brightness of Aoki's road, we say that Takahashi's road is brighter at that time.

Among the integer times from time 1 to time T inclusive, find the total number of times when Takahashi's road is brighter.

Note that the lighting operation times or the subsequent lighting periods may exceed time T, but only integer times from 1 to T inclusive are counted.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq D \leq 10^9
• 1 \leq T \leq 10^9
• 1 \leq A_i \leq T (1 \leq i \leq N)
• 1 \leq B_j \leq T (1 \leq j \leq M)
• All inputs are integers

Sample Input 1

3 2 3 8
1 4 4
2 5

Sample Output 1

4

Sample Input 2

4 3 1 6
3 1 3 6
1 2 3

Sample Output 2

2

Sample Input 3

12 10 5 30
3 10 10 1 25 18 7 22 14 14 29 5
2 8 8 12 16 20 24 28 30 4

Sample Output 3

15

Sample Input 4

30 28 7 100
5 12 12 18 25 31 37 42 42 49 53 60 67 70 75 80 85 90 95 99 1 8 15 22 29 36 43 50 57 64
3 10 17 24 24 31 38 45 52 59 66 73 80 87 94 100 6 13 20 27 34 41 48 55 62 69 76 83

Sample Output 4

28

Sample Input 5

1 1 1 1
1
1

Sample Output 5

0

Problem Statement

Takahashi has decided to go hiking in a mountainous area. This area consists of N points and M trails, where each trail can be traversed in both directions. Takahashi starts at the trailhead at point 1 and aims to reach the summit at point N.

Each point i (1 \leq i \leq N) has a "danger level" P_i assigned to it. This represents the level of risk of natural disasters such as rockfalls or landslides at that point. Additionally, the j-th (1 \leq j \leq M) trail bidirectionally connects point U_j and point V_j, and it takes W_j time to traverse. We assume that the time spent staying at any point is negligible.

Takahashi starts from point 1 and repeatedly traverses trails to reach point N. He is allowed to visit the same point or traverse the same trail multiple times. The travel time of a route is the sum of the times of the traversed trails. The danger level of a route is the maximum danger level among all points visited along the route, including the start point 1 and the destination point N.

Takahashi wants to enjoy hiking as safely as possible, but he must reach the summit before sunset. Specifically, he wants to minimize the danger level of the route among all routes whose travel time is at most T.

It is guaranteed that there is at least one route from point 1 to point N with a travel time of at most T. Find the minimum possible danger level of a route satisfying the conditions.

Constraints

• 2 \leq N \leq 2 \times 10^4
• 1 \leq M \leq 4 \times 10^4
• 1 \leq T \leq 10^9
• 0 \leq P_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
• U_j \neq V_j (1 \leq j \leq M)
• 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
• There may be multiple trails connecting the same pair of points.
• There is at least one route from point 1 to point N with a travel time of at most T.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

8

Sample Input 3

10 18 25
10 30 5 40 20 15 60 25 35 12
1 2 5
2 10 15
1 3 4
3 6 7
6 10 12
3 4 3
4 10 5
1 5 10
5 8 5
8 10 9
2 5 2
5 6 2
6 7 3
7 10 3
2 3 8
4 8 2
8 9 4
9 10 4

Sample Output 3

15

Sample Input 4

20 40 100
50 12 80 7 30 65 18 90 22 55 5 70 35 42 15 100 28 60 10 40
1 2 10
2 4 10
4 7 8
7 11 12
11 15 10
15 19 9
19 20 8
1 3 5
3 6 5
6 10 15
10 14 10
14 20 20
1 5 20
5 9 10
9 13 15
13 17 10
17 20 20
2 5 6
5 7 7
7 9 5
9 11 6
11 13 7
13 15 5
15 17 6
17 19 4
3 8 12
8 12 8
12 16 10
16 20 25
4 8 20
6 12 15
10 16 10
14 18 6
18 20 10
2 6 30
5 10 25
9 14 20
13 18 12
3 4 50
12 19 30

Sample Output 4

50

Sample Input 5

2 1 1000000000
0 1000000000
1 2 1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is working part-time at a moving company. There are N items in the warehouse, and the weight of the i-th item (1 \leq i \leq N) is W_i.

All of these items must be loaded into trucks and transported. We can prepare as many trucks as we need, and each truck has the same maximum capacity of M.

The loading of items must satisfy the following conditions:

• Each item cannot be divided, and each of the N items must be loaded onto exactly one truck.
• The total weight of the items loaded onto a single truck must be at most the maximum capacity M.
• Each truck can make only one trip. It is not possible to make multiple trips with the same truck.

Find the minimum number of trucks required to transport all the items.

Note that because of the constraint W_i \leq M, each item can be loaded onto a truck by itself, so it is always possible to transport all the items.

Constraints

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

Sample Input 1

4 10
2 5 4 7

Sample Output 1

2

Sample Input 2

5 10
6 6 4 4 2

Sample Output 2

3

Sample Input 3

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

Sample Output 3

4

Sample Input 4

20 50
24 26 10 40 15 35 5 45 20 30 25 25 12 18 32 8 42 7 13 37

Sample Output 4

10

Sample Input 5

1 1000000000
1000000000

Sample Output 5

1