Problem Statement

Takahashi has a hobby of weather observation and records the daily high temperature. He has recorded temperatures over N days.

The highest temperature recorded on day i (1 \leq i \leq N) is A_i ℃.

Takahashi is interested in periods where the temperatures on consecutive days are strictly increasing. Specifically, for integers l, k satisfying 1 \leq l and l + k - 1 \leq N, if the temperatures over the k days from day l to day l+k-1 satisfy

A_l < A_{l+1} < \cdots < A_{l+k-1}

then these k days are called a rising period of length k. When k=1, the condition is trivially satisfied, so any single day is a rising period of length 1.

Takahashi wants to know the length (in days) of the longest rising period in his N days of recorded data. Find this maximum value.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -40 \leq A_i \leq 45
• All inputs are integers

Sample Input 1

7
20 22 21 23 25 27 24

Sample Output 1

4

Sample Input 2

12
15 18 20 19 17 18 19 20 21 22 20 21

Sample Output 2

6

Sample Input 3

20
-5 -3 0 2 5 8 12 15 14 13 10 11 12 13 14 15 16 17 18 20

Sample Output 3

10

Problem Statement

N children are sitting in a circle. The children are numbered from 1 to N, and they are arranged in clockwise order as child 1, child 2, \ldots, child N (the clockwise neighbor of child N is child 1). Initially, child i holds exactly one card with the number i written on it.

The following operation is repeated K times:

• Everyone simultaneously passes their card to the child next to them in the clockwise direction. That is, child i (1 \leq i \leq N-1) passes their card to child i+1, and child N passes their card to child 1.

In each operation, everyone passes exactly one card and receives exactly one card, so after the operation each child still holds exactly one card.

After K operations, determine the number written on the card that each child is holding.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq 10^{18}
• All input values are integers

Sample Input 1

5 2

Sample Output 1

4
5
1
2
3

Sample Input 2

6 0

Sample Output 2

1
2
3
4
5
6

Sample Input 3

12 25

Sample Output 3

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

Sample Input 4

1 1000000000000000000

Sample Output 4

1

Problem Statement

Takahashi is shopping at a supermarket. There are N items in the store, and the i-th item (1 \leq i \leq N) has a satisfaction value of V_i and a price of C_i yen. Each item can be purchased at most once.

Takahashi has S yen on hand. He wants to spend exactly S yen.

Consider selecting and purchasing 1 or more items from the N items. If there exists a way to select items such that the total price is exactly S yen, find the maximum total satisfaction among all such selections.

If no selection of items has a total price of exactly S yen, output -1.

Constraints

• 1 \leq N \leq 3000
• 1 \leq S \leq 10000
• 1 \leq V_i \leq 10000 (1 \leq i \leq N)
• 1 \leq C_i \leq 10000 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 5
3 2
4 3
1 4

Sample Output 1

7

Sample Input 2

3 10
1 3
2 3
3 3

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

31

Sample Input 4

15 50
20 8
15 12
30 10
25 15
10 5
18 7
12 9
22 14
8 3
35 20
14 6
9 11
27 13
19 16
11 4

Sample Output 4

124

Sample Input 5

1 7
5 7

Sample Output 5

5

Problem Statement

Takahashi is the administrator of a corporate network. The network has N terminals connected to it, numbered from 1 to N. Each terminal is in one of two states: "infected" or "not infected," but Takahashi does not know which terminals are infected.

Takahashi performed M scans. Each scan j (1 \leq j \leq M) examines a specified set of K_j terminals \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\} at once and returns a result R_j.

• R_j = 1 ("infection detected"): The set contains at least one infected terminal.
• R_j = 0 ("no infection"): The set contains no infected terminals.

Note that the sets of terminals examined by different scans may overlap or even be identical.

Here, a method of assigning either "infected" or "not infected" to each terminal is called an infection status assignment. An assignment is said to be consistent with all scan results if, for every scan j (1 \leq j \leq M), the following conditions are satisfied:

• When R_j = 1: Among the set \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\}, there exists at least one terminal assigned as infected.
• When R_j = 0: Among the set \{S_{j,1}, S_{j,2}, \ldots, S_{j,K_j}\}, there are no terminals assigned as infected.

It is guaranteed that at least one assignment consistent with all scan results exists. Among all such assignments, find the minimum number of infected terminals.

Constraints

• 1 \leq N \leq 16
• 1 \leq M \leq 100
• 1 \leq K_j \leq N (1 \leq j \leq M)
• 1 \leq S_{j,k} \leq N (1 \leq j \leq M, 1 \leq k \leq K_j)
• For each scan j, the values S_{j,1}, S_{j,2}, \ldots, S_{j,K_j} are all distinct.
• R_j \in \{0, 1\} (1 \leq j \leq M)
• There exists at least one infection status assignment consistent with all scan results.
• All input values are integers.

Sample Input 1

3 2
2 1 2 1
2 2 3 0

Sample Output 1

1

Sample Input 2

5 4
3 1 2 3 1
2 4 5 1
2 1 4 0
2 2 5 1

Sample Output 2

2

Sample Input 3

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

Sample Output 3

2

Problem Statement

Takahashi is an adventurer. He is traveling across a continent containing N towns.

The N towns are numbered from 1 to N, and there are M roads connecting the towns. The i-th road bidirectionally connects town U_i and town V_i, and traveling along this road costs W_i stamina.

Takahashi's initial stamina is F. He starts at town 1 and wants to reach town N.

Each town j has an inn with a recovery value R_j. When Takahashi visits a town for the first time, the inn in that town restores R_j stamina. This recovery is applied only once per town — if he visits the same town two or more times, no recovery occurs from the second visit onward. Note that there is no upper limit on stamina (it can grow arbitrarily large through recovery).

Town 1 is treated as being visited for the first time at the moment of departure. Therefore, Takahashi's stamina before making the first move is F + R_1.

Takahashi's movement is performed by repeating the following steps:

1. Takahashi chooses one road connected to the town he is currently in. However, he can only choose a road whose traversal cost (W_i) is less than or equal to his current stamina. If no road satisfies this condition, Takahashi cannot move any further.
2. He travels along the chosen road, and his stamina decreases by W_i. It is acceptable for his stamina to become exactly 0.
3. Immediately after arriving at the destination town, if this is his first visit to that town, the inn's recovery value R_j is added to his stamina.

Takahashi may travel along the same road any number of times and may visit the same town any number of times (however, inn recovery is applied only once per town as described above).

Considering all possible ways Takahashi can travel from town 1 to town N, find the maximum stamina upon arrival at town N. Here, the stamina upon arrival at town N refers to the stamina after step 3 above has been applied (if town N is visited for the first time, the inn recovery at town N is also applied).

If it is impossible to reach town N regardless of how he moves, output -1.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \frac{N(N-1)}{2}
• 0 \leq F \leq 1000
• 0 \leq R_j \leq 1000 (1 \leq j \leq N)
• 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
• 1 \leq W_i \leq 1000 (1 \leq i \leq M)
• There is at most one road connecting any pair of towns
• All input values are integers

Sample Input 1

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

Sample Output 1

11

Sample Input 2

3 1 5
0 0 0
1 2 3

Sample Output 2

-1

Sample Input 3

5 6 10
5 100 3 2 8
1 2 12
1 3 5
2 3 8
2 5 10
3 4 3
4 5 3

Sample Output 3

103

Sample Input 4

8 10 50
10 20 30 40 50 15 25 100
1 2 30
1 3 40
1 6 35
2 3 25
3 4 20
3 8 80
4 5 15
5 8 10
6 7 20
7 8 30

Sample Output 4

200

Sample Input 5

2 1 0
1000 1000
1 2 1000

Sample Output 5

1000