Problem Statement

Takahashi manages N smartphones. The current battery level of the i-th smartphone is W_i percent.

The battery of a smartphone decreases by D percentage points per day if not charged.

Takahashi is considering ordering from an online charger store. If he places an order, the charger will arrive in exactly K days. Since Takahashi currently has no charger, he cannot charge any smartphone during the K days until it arrives.

After K days, when the charger arrives, the battery level of the i-th smartphone is considered to be W_i - D \times K percent. A smartphone with this value being 1 or more is still usable, while a smartphone with this value less than 1 has powered off and become unusable.

Determine the number of smartphones among the N that are still usable after K days.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq D \leq 100
• 1 \leq K \leq 10^9
• 1 \leq W_i \leq 100 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 10 5
100 50 30

Sample Output 1

1

Sample Input 2

5 15 3
80 45 46 20 100

Sample Output 2

3

Sample Input 3

10 7 10
100 70 71 50 35 28 1 72 99 65

Sample Output 3

4

Problem Statement

Takahashi took final exams in N subjects. In each subject i (1 \leq i \leq N), Takahashi scored A_i points.

At Takahashi's school, if there is even one subject where the score is below the target score of T points, the student must attend supplementary lessons.

Fortunately, this school has an "extra assignment system." For each extra assignment submitted, Takahashi can choose any one subject and increase that subject's score by 1 point. The same subject may be chosen multiple times. There is no upper limit on the score for each subject. However, the total number of extra assignments that can be submitted is at most M. It is also allowed to submit no extra assignments at all.

Takahashi wants to avoid supplementary lessons by strategically submitting extra assignments so that all subjects' scores become at least T points.

Determine whether it is possible to achieve a score of at least T in all subjects by submitting a total of at most M extra assignments. If it is possible, output the minimum number of extra assignments needed. If all subjects already have scores of at least T, output 0. If it is impossible, output -1.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq 10^9
• 0 \leq T \leq 100
• 0 \leq A_i \leq 100 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 5 60
55 70 58

Sample Output 1

-1

Sample Input 2

5 10 80
75 80 90 60 85

Sample Output 2

-1

Sample Input 3

10 1000000000 70
65 70 72 68 55 80 90 45 70 71

Sample Output 3

47

Problem Statement

Takahashi works at the road management division of the city hall. The road surface under his jurisdiction consists of N tiles arranged in a row, numbered tile 1, 2, \ldots, N from left to right.

Among these, M tiles are damaged. The numbers of the damaged tiles are B_1, B_2, \ldots, B_M, all of which are distinct (not necessarily in ascending order).

One day, K cars traveled along this road. The i-th car (1 \leq i \leq K) passes over every tile exactly once in the contiguous section from tile L_i to tile R_i (L_i \leq R_i). Each car's travel does not affect the travel of other cars, and tiles do not change their state when a car passes over them.

Each time a car passes over one damaged tile, one shock occurs. That is, the total number of shocks generated by the i-th car's travel equals the number of damaged tiles contained in the section from tile L_i to tile R_i.

For each car, Takahashi calculates the total number of shocks generated during its travel, and if it is at least the threshold T, he reports that car's travel section as "needs repair." Here, T is given as a positive integer.

For each of the K cars, determine whether its travel section is reported as needing repair.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq N
• 1 \leq K \leq 2 \times 10^5
• 1 \leq T \leq N
• 1 \leq B_i \leq N (1 \leq i \leq M)
• All B_i are distinct
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq K)
• All input values are integers

Sample Input 1

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

Sample Output 1

YES
NO
YES

Sample Input 2

5 1 3 2
3
1 2
3 3
1 5

Sample Output 2

NO
NO
NO

Sample Input 3

20 6 8 3
3 7 10 12 15 18
1 20
1 5
5 15
10 18
1 2
14 16
6 13
11 14

Sample Output 3

YES
NO
YES
YES
NO
NO
YES
NO

Sample Input 4

50 10 12 4
31 5 44 17 28 12 49 36 23 40
1 50
1 10
10 30
20 45
1 4
5 5
30 50
15 25
35 50
1 28
43 46
25 42

Sample Output 4

YES
NO
YES
YES
NO
NO
YES
NO
YES
YES
NO
YES

Sample Input 5

1 1 1 1
1
1 1

Sample Output 5

YES

Problem Statement

Takahashi has a decorative panel with N light bulbs arranged in a row. The bulbs are numbered from 1 to N from left to right, and each bulb is in one of two states: "on" or "off".

The initial state of each bulb is given by an integer A_i. When A_i = 0, bulb i is on, and when A_i = 1, bulb i is off.

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

• Choose an integer i (1 \leq i \leq N - K + 1) and toggle the states of bulbs i, i+1, \ldots, i+K-1. That is, among these K consecutive bulbs, those that are on are turned off, and those that are off are turned on.

The value of i chosen in each operation can be decided freely each time, and it is allowed to choose the same value as before.

Takahashi wants to turn all bulbs on (that is, reach the state where A_i = 0 for all i). Determine whether this is possible, and if so, find the minimum number of operations required.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• A_i \in \{0, 1\} (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 3
0 1 1 1 0

Sample Output 1

1

Sample Input 2

4 2
1 0 0 1

Sample Output 2

3

Sample Input 3

10 3
1 1 1 0 0 0 1 1 1 0

Sample Output 3

2

Problem Statement

There are N towns in a region, numbered from 1 to N. Some towns are connected by roads, all of which are bidirectional, and there are M roads in total. The i-th road connects town U_i and town V_i, and the time required to travel along this road is W_i. Note that it is not necessarily the case that all towns are reachable from each other via roads.

Takahashi is a delivery driver. He must depart from the distribution center located in town 1, deliver packages to all N towns, and then return to the distribution center in town 1. Specifically, he starts from town 1, repeatedly moves from town to town via roads, visits every town at least once, and finally returns to town 1. He is allowed to visit the same town multiple times and traverse the same road multiple times.

Find the minimum total travel time of roads traversed along such a route. If the same road is traversed multiple times, its travel time is added each time it is traversed. If no valid route exists, output -1.

Constraints

• 2 \leq N \leq 15
• 1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i (no self-loops)
• If i \neq j, then \{U_i, V_i\} \neq \{U_j, V_j\} (there is at most one road between any pair of towns)
• 1 \leq W_i \leq 10^6
• All input values are integers

Sample Input 1

4 4
1 2 10
2 3 15
3 4 20
4 1 25

Sample Output 1

70

Sample Input 2

4 2
1 2 5
3 4 8

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

30