Problem Statement

Takahashi is a lecturer at a cram school. At this school, students from N classes took a mock exam.

Each class i (1 \leq i \leq N) has A_i students, and each student's exam score has been recorded. The score of the j-th student (1 \leq j \leq A_i) in class i is B_{i,j} points.

Takahashi set a passing score of K points as the passing criterion. A student whose score is K points or higher is judged as passing.

Find the total number of students judged as passing across all classes.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq K \leq 100
• 1 \leq A_i \leq 100
• \sum_{i=1}^{N} A_i \leq 10^6 (the total number of students across all classes is at most 10^6)
• 0 \leq B_{i,j} \leq 100
• All input values are integers

Sample Input 1

3 60
4 45 72 60 88
3 59 60 61
2 100 30

Sample Output 1

6

Sample Input 2

5 70
5 65 70 80 55 90
3 69 71 70
4 100 85 72 68
2 50 49
6 75 80 85 90 95 100

Sample Output 2

14

Sample Input 3

10 50
8 23 45 67 89 12 34 56 78
5 50 50 50 49 51
10 0 10 20 30 40 50 60 70 80 90
3 100 100 100
7 45 46 47 48 49 50 51
4 25 75 25 75
6 99 98 97 96 95 94
2 0 100
9 55 55 55 55 55 44 44 44 44
5 1 2 3 4 5

Sample Output 3

32

Problem Statement

Takahashi is a member of the university's scholarship selection committee. This year, there are N types of scholarships, and for each one, a recipient must be determined from among the students who applied.

The university has M applicants, and applicant j (1 \leq j \leq M) has been assigned an evaluation score P_j based on their academic performance. The evaluation score is a fixed value for each applicant, and a higher value means a higher evaluation. It is possible for different applicants to have the same evaluation score.

A single applicant may apply for multiple scholarships. Since the recipient of each scholarship is determined independently, a single applicant may receive multiple scholarships.

For each scholarship i (1 \leq i \leq N), the applicant numbers C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} of the K_i applicants who applied for that scholarship are given. The recipient is determined by the following rules:

• If there are no applicants (K_i = 0), there is no recipient for that scholarship.
• If there are applicants, the applicant with the highest evaluation score receives the scholarship. If there are multiple applicants with the highest evaluation score, the one with the smallest applicant number among them receives it.

For each scholarship, determine the applicant number of the person who ultimately receives that scholarship. If there is no recipient, output 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq P_j \leq 10^9 (1 \leq j \leq M)
• 0 \leq K_i \leq M (1 \leq i \leq N)
• 1 \leq C_{i,k} \leq M (1 \leq i \leq N, 1 \leq k \leq K_i)
• The same applicant does not appear multiple times for the same scholarship (C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} are distinct)
• \displaystyle \sum_{i=1}^{N} K_i \leq 2 \times 10^5
• All input values are integers

Sample Input 1

3 4
100 80 100 90
2 1 2
3 2 3 4
0

Sample Output 1

1
3
0

Sample Input 2

5 6
50 50 50 30 70 70
3 1 2 3
2 5 6
4 1 4 5 6
1 4
0

Sample Output 2

1
5
5
4
0

Sample Input 3

8 10
1000000000 999999999 500000000 750000000 1000000000 250000000 750000000 100000000 999999999 500000000
5 1 2 3 4 5
3 6 7 8
4 2 5 9 10
0
2 1 5
6 1 2 3 4 5 6
1 8
10 1 2 3 4 5 6 7 8 9 10

Sample Output 3

1
7
5
0
1
1
8
1

Problem Statement

Takahashi is planning to visit N shopping malls in the suburbs to shop during a weekend sale.

Each shopping mall i (1 \leq i \leq N) has M_i stores, each selling sale items. If Takahashi shops at the j-th store (1 \leq j \leq M_i) of shopping mall i, he can gain a benefit value of P_{i,j} yen.

To visit shopping mall i, he must pay a visiting cost of C_i yen. This cost is a fixed value determined for each mall.

Due to time constraints, Takahashi can choose and visit at most K malls out of the N malls (it is also possible to visit none). He cannot visit the same mall more than once.

At each mall he visits, he can choose any number (zero or more) of stores from the M_i stores in that mall to shop at. He can shop at each store at most once. Note that even if he does not choose any store at a mall he visits, he still must pay the visiting cost C_i.

Maximize the total profit that Takahashi can obtain. The total profit is defined as follows:

\text{Total profit} = \sum_{\text{stores } (i,j) \text{ where he shopped}} P_{i,j} - \sum_{\text{malls } i \text{ he visited}} C_i

In other words, it is the sum of benefit values of all stores where he shopped, minus the sum of visiting costs of all malls he visited. If he visits no malls, the total profit is 0. Therefore, the maximum total profit is at least 0.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq K \leq N
• 1 \leq M_i \leq 100
• \sum_{i=1}^{N} M_i \leq 10^5
• 1 \leq C_i \leq 10^9
• 1 \leq P_{i,j} \leq 10^9
• All input values are integers

Sample Input 1

3 2
500 3 200 300 100
300 2 400 150
800 4 250 250 250 250

Sample Output 1

450

Sample Input 2

4 3
100 2 50 60
200 3 300 100 50
150 1 100
80 2 90 85

Sample Output 2

355

Sample Input 3

5 2
1000000000 5 500000000 400000000 300000000 200000000 100000000
100 3 50 40 30
999999999 2 1000000000 1000000000
500 4 200 150 100 80
10000 10 5000 4000 3000 2000 1000 900 800 700 600 500

Sample Output 3

1500000001

Problem Statement

Takahashi is participating in an orienteering competition. In this competition, he must visit designated checkpoints in order and reach the goal.

The competition venue has N locations, numbered from 1 to N. There are M bidirectional roads between these locations. The i-th road (1 \leq i \leq M) connects location U_i and location V_i, and takes T_i minutes to traverse in either direction. There may be multiple roads connecting the same pair of locations. Also, it is not guaranteed that all locations are reachable from each other via roads.

Takahashi is currently at location 1, the starting point. According to the competition rules, he must visit K designated checkpoints P_1, P_2, \ldots, P_K in this exact order, and finally arrive at location N, the goal. Specifically, he departs from location 1 and reaches location P_1, then reaches location P_2, \ldots, reaches location P_K, and finally arrives at location N.

The rules regarding checkpoint visits are as follows:

• Checkpoints are completed only in the order P_1, P_2, \ldots, P_K. When arriving at a location, if that location is the next checkpoint to be visited, the visit to that checkpoint is completed immediately. No time other than travel time is incurred.
• Since Takahashi starts at location 1, if P_1 = 1, the visit to checkpoint P_1 is completed at the moment of departure. In general, when a checkpoint visit is completed, if the next checkpoint to be visited is the same as the current location, that checkpoint's visit is also completed immediately.
• Even if you pass through a location of a checkpoint whose turn has not yet come, that checkpoint is not completed. You must either already be at that location when its turn comes, or revisit it.
• The designated checkpoint numbers are not necessarily distinct from each other, and may coincide with location 1 or location N.

Throughout the entire journey, you may pass through the same location or the same road any number of times.

Since Takahashi aims to win, he wants to reach the goal in the shortest possible time. Find the minimum total travel time (in minutes) to depart from location 1, visit P_1, P_2, \ldots, P_K in order, and then arrive at location N. If no valid route exists, output -1.

Constraints

• 2 \leq N \leq 5 \times 10^4
• 1 \leq M \leq 10^5
• 1 \leq K \leq 10
• 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
• U_i \neq V_i (1 \leq i \leq M)
• There may be multiple roads connecting the same pair of locations
• 1 \leq T_i \leq 10^9 (1 \leq i \leq M)
• 1 \leq P_j \leq N (1 \leq j \leq K)
• The P_j values are not necessarily distinct
• The graph is not necessarily connected
• All input values are integers

Sample Input 1

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

Sample Output 1

11

Sample Input 2

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

Sample Output 2

15

Sample Input 3

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

Sample Output 3

13

Problem Statement

Takahashi will water his field over N days. Each day, he chooses and executes exactly one of two watering methods.

Method A is a method that spreads a large amount of water all at once. On a day when this method is chosen, it basically yields a growth amount of a, but because too much water is spread, the soil becomes waterlogged, and the growth amount obtained on the next day is halved (there is no effect on days after that).

Method B is a method that carefully spreads a small amount of water. On a day when this method is chosen, it basically yields a growth amount of b. Since there is no burden on the soil, there is no negative effect on the next day.

Specifically, the growth amount for each day is determined by the following rules:

• If Method B was used on the previous day, or if it is the first day (no previous day exists), no halving occurs. If Method A is chosen, the growth amount is a; if Method B is chosen, the growth amount is b.
• If Method A was used on the previous day, the growth amount for that day is halved. If Method A is chosen, the growth amount is \lfloor a / 2 \rfloor; if Method B is chosen, the growth amount is \lfloor b / 2 \rfloor. Here, \lfloor x \rfloor denotes the largest integer not exceeding x.

The halving is always applied to the base values a or b. It does not matter whether the previous day's growth amount was itself halved; the determination is based solely on "whether Method A was used on the previous day." For example, if Method A is chosen for three consecutive days, the growth amounts are a on the first day, \lfloor a/2 \rfloor on the second day, and \lfloor a/2 \rfloor on the third day.

Find the maximum possible total growth amount when the watering methods over the N days are chosen optimally.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq a \leq 10^9
• 1 \leq b \leq 10^9
• All input values are integers.

Sample Input 1

5 10 3

Sample Output 1

32

Sample Input 2

4 3 5

Sample Output 2

20

Sample Input 3

100 100 51

Sample Output 3

6276

Sample Input 4

1000000000000 100000 1

Sample Output 4

50000000000050000

Sample Input 5

1 1 1

Sample Output 5

1