Problem Statement

Takahashi is a librarian at a certain library. Recently, he decided to record visitor data over D days in order to analyze the library's usage.

The library has N registered users, each assigned a user ID from 1 to N. For each of the D days, Takahashi recorded the user IDs of the visitors who came that day. On day j (1 \leq j \leq D), there were M_j visitors, and their user IDs are S_{j,1}, S_{j,2}, \ldots, S_{j,M_j}. Note that the same user is never recorded multiple times on the same day. Also, the user IDs within each day's record are not necessarily in any particular order.

Takahashi defines a "regular user" as a user who visited the library on at least K of the D days, and he wants to compile a list of all regular users. Here, the number of days a user visited is the number of days on which that user's ID appears in the visitor records.

Given the visitor records for D days, output all user IDs that are identified as regular users in ascending order. If there are no regular users, output -1.

Constraints

• 1 \leq N \leq 100
• 1 \leq D \leq 100
• 1 \leq K \leq D
• 0 \leq M_j \leq N (1 \leq j \leq D)
• 1 \leq S_{j,i} \leq N (1 \leq j \leq D, \; 1 \leq i \leq M_j)
• The same user ID does not appear multiple times within the same day's record
• All input values are integers

Sample Input 1

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

Sample Output 1

2 3

Sample Input 2

4 3 3
2 1 2
2 3 4
2 1 3

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

1 2 3 4 6

Sample Input 4

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

Sample Output 4

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

Sample Input 5

1 1 1
0

Sample Output 5

-1

Problem Statement

Takahashi is the manager of a vast botanical garden. The garden has N flower beds, each placed at a distinct position on a plane. The coordinates of flower bed i (1 \leq i \leq N) are (X_i, Y_i).

Note that different flower beds may share the same X coordinate or the same Y coordinate.

Takahashi has decided to create a layout map summarizing the positions of all flower beds. The layout map is a grid defined as follows.

Let C_x be the number of distinct values among the X coordinates of the N flower beds, and C_y be the number of distinct values among the Y coordinates. Let the distinct X coordinate values in ascending order be x_1 < x_2 < \cdots < x_{C_x}, and the distinct Y coordinate values in ascending order be y_1 < y_2 < \cdots < y_{C_y}.

The layout map is a grid consisting of C_x \times C_y cells. Each cell corresponds one-to-one with an index pair (p, q) (1 \leq p \leq C_x, 1 \leq q \leq C_y), where cell (p, q) represents the coordinates (x_p, y_q).

For each flower bed i with coordinates (X_i, Y_i), there exists exactly one p and one q such that X_i = x_p and Y_i = y_q, so flower bed i is placed in cell (p, q). Since all flower bed coordinates are distinct, each flower bed is placed in a different cell, and the number of cells containing a flower bed is exactly N.

The number of empty cells in the layout map is defined as the total number of cells minus the number of flower beds, namely C_x \times C_y - N.

Now, Aoki (Takahashi's colleague) has given Takahashi an additional task: for each flower bed, determine the number of empty cells in the layout map created from the remaining N - 1 flower beds when that flower bed is removed.

Specifically, for each i = 1, 2, \ldots, N, create the layout map using the above procedure for the remaining N - 1 flower beds after removing flower bed i. Let C'_x be the number of distinct values among the X coordinates and C'_y be the number of distinct values among the Y coordinates of the remaining N - 1 flower beds. The number of empty cells is C'_x \times C'_y - (N - 1). Compute this value for each i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i \leq 10^9
• -10^9 \leq Y_i \leq 10^9
• (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
• All input values are integers

Sample Input 1

4
1 1
1 2
2 1
3 3

Sample Output 1

6
3
3
1

Sample Input 2

3
0 0
1 1
2 2

Sample Output 2

2
2
2

Sample Input 3

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

Sample Output 3

11
11
11
11
11
11
11
11
11
11

Sample Input 4

20
-10 4
-10 7
-5 2
-5 4
-5 9
0 1
0 4
0 7
0 9
3 2
3 7
3 9
6 1
6 2
6 4
8 1
8 7
8 9
10 2
10 4

Sample Output 4

16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16

Sample Input 5

2
1000000000 -1000000000
-1000000000 1000000000

Sample Output 5

0
0

Problem Statement

Takahashi was planning to go to a department store's closing sale, but he accidentally took a nap and arrived late.

The department store sale starts at time 0 minutes and the store closes at time T minutes. Takahashi arrives at the department store at time S minutes (0 \leq S \leq T). He can shop during the remaining T - S minutes from his arrival time S until the closing time T.

There are N items at the sale venue. Purchasing the i-th item (1 \leq i \leq N) requires C_i minutes of purchase processing time, and buying it yields a savings value of P_i yen. Each item can be purchased at most once.

Takahashi can only process the purchase of one item at a time. Once the purchase processing of an item is completed, he can immediately start processing the next item. No time is required other than purchase processing. Also, purchase processing cannot be interrupted midway, and all processing must be completed by the closing time.

Therefore, if A is the set of items to purchase, the total purchase processing time must not exceed the remaining time, i.e., \displaystyle\sum_{i \in A} C_i \leq T - S must be satisfied.

Under this condition, find the maximum total savings value \displaystyle\sum_{i \in A} P_i that Takahashi can obtain.

Constraints

• 1 \leq N \leq 100
• 1 \leq T \leq 10^4
• 0 \leq S \leq T
• 1 \leq C_i \leq 10^4
• 1 \leq P_i \leq 10^5
• All inputs are integers

Sample Input 1

3 10 7
2 100
3 150
4 200

Sample Output 1

150

Sample Input 2

5 100 85
5 300
8 500
10 600
3 200
7 450

Sample Output 2

950

Sample Input 3

8 5000 4970
12 800
9 550
15 900
6 400
8 600
10 700
5 350
3 200

Sample Output 3

2100

Problem Statement

Takahashi has N debts.

Each debt i (1 \leq i \leq N) has an initial balance of H_i yen and a fixed interest amount of G_i yen that is added every turn.

Takahashi repays these debts in a turn-based manner. At the beginning of each turn, Takahashi receives P yen. This P yen can only be used within that turn, and any unused portion disappears at the end of the turn.

Each turn proceeds as follows:

1. Repayment Phase: Takahashi chooses one debt that has not yet been fully repaid and pays it off completely, or chooses to do nothing. However, he can only choose a debt whose current balance is at most P. When paying off a debt, he pays an amount equal to that debt's balance, and that debt disappears thereafter (its balance becomes 0). Any portion of the P yen not used for payment simply disappears and cannot be carried over to the next turn. Partial repayment (paying only a portion of the balance) is not allowed. At most 1 debt can be fully repaid per turn.
2. Interest Phase: After the repayment phase ends, for every debt i that has not yet been fully repaid, its balance increases by G_i yen.

At the start of the repayment phase of the first turn, the balance of each debt i is the initial balance H_i yen.

Determine whether Takahashi can fully repay all debts within a finite number of turns if he repays them in the optimal order. If he can, output Yes; otherwise, output No.

Constraints

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

Sample Input 1

3 10
6 2
2 1
8 1

Sample Output 1

Yes

Sample Input 2

3 10
9 2
10 1
3 1

Sample Output 2

No

Sample Input 3

10 100
80 5
70 10
95 1
40 15
10 10
60 4
99 1
50 8
30 7
20 20

Sample Output 3

Yes

Sample Input 4

25 1000000
851860 12345
1000000 99999
200008 33333
725932 45678
622226 22222
700000 150000
200000 40000
111115 98765
555556 111111
185185 54321
76000 42000
222223 777777
340000 60000
430000 30000
904947 13579
57000 41000
250000 250000
90000 65000
111120 88888
382720 123456
200008 44444
90000 70000
200008 99999
55000 45000
111120 55555

Sample Output 4

Yes

Sample Input 5

1 1000000000
1000000000 1000000000

Sample Output 5

Yes

Problem Statement

Takahashi is climbing a mountain from the foot to the observatory at the summit.

There are N checkpoints on this mountain, numbered 1 to N. Additionally, the foot of the mountain is represented as point 0, and the observatory at the summit is represented as point N+1.

Takahashi starts at point 0 (the foot), visits some chosen checkpoints among the N checkpoints as he climbs, and finally reaches point N+1 (the observatory at the summit). Takahashi always moves in the direction of increasing point numbers (thus, he visits each checkpoint at most once). That is, if the indices of the visited checkpoints in ascending order are p_1 < p_2 < \cdots < p_s, Takahashi moves in the following order:

0 \to p_1 \to p_2 \to \cdots \to p_s \to N+1

If s = 0 (no checkpoints are visited), he moves directly from point 0 to point N+1.

For any pair of points (a, b) satisfying 0 \leq a < b \leq N+1, a cost C_{a,b} is defined for moving directly from point a to point b without passing through any checkpoints in between. That is, direct movement is possible even between two non-adjacent points, and its cost is given. The total stamina consumption of the entire route is the sum of the costs between consecutive points on the route. Specifically, the stamina consumption for the route above is:

C_{0,\,p_1} + C_{p_1,\,p_2} + \cdots + C_{p_{s-1},\,p_s} + C_{p_s,\,N+1}

(or C_{0,\,N+1} if s = 0).

There are two rules for choosing which checkpoints to visit:

1. Minimum Count Condition: The number of visited checkpoints s must be at least K.
2. Terrain Balance Condition: Each checkpoint is classified into exactly one of M terrain types, represented by integers from 1 to M. For each integer j (1 \leq j \leq M), the number of visited checkpoints belonging to terrain type j must be even (where 0 is also considered even).

Takahashi wants to find a way to choose checkpoints that satisfies all the rules above while minimizing the total stamina consumption.

If there exists a valid choice of checkpoints, output the minimum stamina consumption. If no such choice exists, output -1.

Constraints

• 1 \leq N \leq 150
• 1 \leq M \leq 8
• N^3 \cdot 2^M \leq 3 \times 10^8
• 0 \leq K \leq N
• 1 \leq t_i \leq M (1 \leq i \leq N)
• 1 \leq C_{a,b} \leq 10^9 (0 \leq a < b \leq N+1)
• All input values are integers.

Sample Input 1

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

Sample Output 1

17

Sample Input 2

1 1 1
1
3 10
4

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

28

Sample Input 4

15 5 6
1 2 3 4 5 1 2 3 4 5 1 2 3 4 1
11 25 18 40 33 52 47 60 58 75 69 88 80 95 90 110
14 9 27 22 41 36 55 50 68 63 82 77 96 91 105
13 26 12 39 31 45 44 62 57 70 66 84 79 98
8 21 34 16 48 30 53 47 65 59 78 72 90
17 11 29 24 42 37 56 51 69 64 83 78
10 23 15 36 28 49 41 54 52 71 67
19 14 32 27 46 40 58 53 72 68
12 25 20 38 33 51 45 63 60
16 9 30 22 43 35 57 49
18 13 31 26 44 39 61
7 24 19 37 32 50
15 28 10 41 34
20 12 35 29
6 27 21
18 14
9

Sample Output 4

100

Sample Input 5

1 1 0
1
1000000000 1
999999999

Sample Output 5

1