Problem Statement

Takahashi is investigating local weather data as part of his summer vacation independent research project. For a period of N days, the daily maximum temperature (°C) has been recorded as an integer value.

The maximum temperatures on day 1, day 2, …, day N are A_1, A_2, \ldots, A_N °C, respectively. A day whose maximum temperature is K °C or higher is called a "hot day."

Takahashi is interested in how many consecutive "hot days" occurred in a row. Specifically, consider a sequence of one or more consecutive days from some day to some day such that every day in the sequence is a "hot day." Find the maximum number of days contained in such a sequence. If there are no "hot days" at all, output 0.

Constraints

• 1 \leq N \leq 10^6
• -50 \leq K \leq 50
• -50 \leq A_i \leq 50 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

10 35
32 36 37 35 33 35 36 37 38 34

Sample Output 1

4

Sample Input 2

15 30
28 30 31 32 29 27 30 30 30 30 30 28 33 34 29

Sample Output 2

5

Sample Input 3

20 0
-5 -3 0 1 2 3 -1 -2 0 0 0 0 0 -4 1 2 3 4 5 -1

Sample Output 3

5

Problem Statement

Takahashi is trying to drive an electric vehicle along a long straight road. This road has N segments, numbered from left to right as segment 1, segment 2, ..., segment N.

The electric vehicle has a battery level, and the initial battery level is K. Takahashi starts just before segment 1 and wants to drive through segments 1, 2, \ldots, N in order from left to right, reaching beyond segment N.

Driving through each segment follows these rules:

• To drive through segment i, the battery level at the start of driving must be 1 or more. If the battery level is 0 or less, the vehicle cannot drive any further, and the journey ends at that point.
• Driving through segment i decreases the battery level by D_i, where D_i is a positive integer representing the consumption of that segment. The battery level after driving may become 0 or less (including negative values), but the driving of that segment itself is completed.

There are M charging stations along the road. Each charging station is at a distinct position, and charging station j is located between segment P_j and segment P_j + 1. Takahashi can use this charging station immediately after completing segment P_j (before starting segment P_j + 1). Charging stations can be used even if the battery level is 0 or less.

When a charging station is used, regardless of the current battery level, the battery is replaced with a new one, and the battery level becomes exactly S_j. Even if the current battery level is greater than S_j, the battery level after replacement becomes S_j. Takahashi can freely choose whether or not to use a charging station; it is not mandatory to use it.

Note that the road is one-way, and it is not possible to return to a previously passed point.

Determine whether Takahashi can drive through all segments and reach beyond segment N by appropriately choosing which charging stations to use. Even if the battery level is 0 or less after completing segment N, as long as the driving of segment N is completed, the journey is considered successful.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq P_j \leq N - 1 (1 \leq j \leq M)
• 1 \leq S_j \leq 10^9 (1 \leq j \leq M)
• P_1 < P_2 < \cdots < P_M (charging stations are given in ascending order of position, and no two charging stations are at the same position)
• All input values are integers

Sample Input 1

5 2 10
3 4 5 2 3
2 8
4 6

Sample Output 1

Yes

Sample Input 2

4 1 5
3 3 3 3
2 4

Sample Output 2

Yes

Sample Input 3

10 4 15
5 3 8 2 6 4 7 3 5 2
2 12
4 20
6 10
8 15

Sample Output 3

Yes

Problem Statement

Takahashi is shopping at a supermarket.

There are N items available at this supermarket, each numbered from 1 to N. The price of item i is P_i yen. Note that different items may have the same price.

Takahashi wants to select and purchase 1 or more of these items such that the total price of the purchased items is exactly K yen. However, each item can be purchased at most once.

Counting two ways as different if the sets of item numbers purchased are different, find the number of ways to purchase items totaling exactly K yen, modulo 10^9 + 7. For example, even if multiple items have the same price, they are counted as different ways if the sets of selected item numbers differ.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 10000
• 1 \leq P_i \leq K
• All inputs are integers

Sample Input 1

4 7
2 3 4 5

Sample Output 1

2

Sample Input 2

6 10
1 2 3 4 5 6

Sample Output 2

5

Sample Input 3

10 100
10 20 30 40 50 15 25 35 45 55

Sample Output 3

21

Problem Statement

Takahashi is in charge of managing the street lights of a shopping district. The shopping district has N street lights arranged in a straight line, numbered from left to right as street light 1, street light 2, \ldots, street light N. The street lights are placed along a line, and street light N and street light 1 are not adjacent. Takahashi is considering replacing some of these street lights with LED lighting.

If street light i (1 \leq i \leq N) is replaced with LED, the annual electricity cost reduction is V_i yen, and the replacement cost is W_i yen. For each street light, you choose either to replace it with LED or not (no street light is replaced more than once). The budget limit given to Takahashi for replacement costs is K yen, so the total replacement cost of the street lights replaced with LED must be at most K yen.

However, there is an old electrical wiring constraint in this shopping district. If two consecutively numbered adjacent street lights are both replaced with LED, the wiring capacity will be exceeded and the breaker will trip. That is, for all i (1 \leq i \leq N-1), it is not allowed to replace both street light i and street light i + 1 with LED.

Find the maximum total annual electricity cost reduction when Takahashi selects which street lights to replace with LED while satisfying both the budget constraint and the wiring constraint. Note that choosing to replace none of the street lights is also allowed. In that case, the total reduction is 0 yen.

Constraints

• 1 \leq N \leq 200
• 1 \leq K \leq 10^4
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq W_i \leq 10^4 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

4 5
100 3
200 2
150 3
80 2

Sample Output 1

280

Sample Input 2

6 10
500 4
300 3
400 5
600 4
200 2
350 3

Sample Output 2

1250

Sample Input 3

10 50
1000000000 8
500000000 12
800000000 10
300000000 5
900000000 15
700000000 9
400000000 7
600000000 11
250000000 6
450000000 8

Sample Output 3

3550000000

Problem Statement

Takahashi is managing a line of \(N\) students. Each student has a unique student ID from \(1\) to \(N\), and the student standing at the \(i\)-th position from the left has student ID \(P_i\). That is, \((P_1, P_2, \ldots, P_N)\) is a permutation of \((1, 2, \ldots, N)\).

Takahashi wants to make this line as close to student ID order (ascending order) as possible. We define the "disorderliness" of the line as the number of pairs \((i, j)\) such that \(i < j\) and \(P_i > P_j\) (the number of inversions).

Takahashi will perform the following operation exactly \(K\) times:

• Choose two adjacent students and swap their positions. That is, choose some \(i\) (\(1 \leq i \leq N - 1\)) and swap \(P_i\) and \(P_{i+1}\).

Find the minimum possible disorderliness (number of inversions) of the line after performing all \(K\) operations.

Note that the same pair of adjacent positions may be chosen multiple times, and operations that undo previous swaps are also allowed.

Constraints

• \(2 \leq N \leq 2 \times 10^5\)
• \(0 \leq K \leq 10^{18}\)
• \((P_1, P_2, \ldots, P_N)\) is a permutation of \((1, 2, \ldots, N)\)
• All input values are integers.

Sample Input 1

5 3
3 1 4 5 2

Sample Output 1

1

Sample Input 2

4 2
1 3 2 4

Sample Output 2

1

Sample Input 3

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

Sample Output 3

4

Sample Input 4

30 123456789012
17 3 25 1 29 12 8 21 5 30 14 2 19 27 10 6 23 15 28 4 11 20 7 26 13 9 24 16 22 18

Sample Output 4

1

Sample Input 5

2 1000000000000000000
1 2

Sample Output 5

0