Problem Statement

Takahashi is conducting an experiment to collect rainwater using N buckets. The buckets are numbered from 1 to N, and bucket i has a capacity of C_i liters. Initially, all buckets are empty.

The buckets are connected in a single line, and water flows as follows. Takahashi continuously pours a total of W liters of water into bucket 1. Water that flows into bucket i (1 \leq i \leq N-1) accumulates in bucket i until it reaches bucket i's capacity C_i. After bucket i becomes full (exactly C_i liters of water have accumulated), any additional water that flows into bucket i will all flow into bucket i+1. After bucket N becomes full, any additional water that flows in will all overflow and be lost.

Determine the number of buckets that are full after all the water has been poured.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq W \leq 10^{18}
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

3 10
3 4 5

Sample Output 1

2

Sample Input 2

5 25
5 10 3 8 6

Sample Output 2

3

Sample Input 3

6 1000000000000000000
100000000 200000000 300000000 400000000 500000000 600000000

Sample Output 3

6

Problem Statement

Takahashi is a library committee member at his school. Today, N students have come to the library to borrow books.

The library lends out M types of books. Each book i (1 \leq i \leq M) has an "interestingness" S_i and a "difficulty" R_i. The difficulty represents the reading comprehension level required to read that book. There are sufficiently many copies of each type of book, so the same type of book can be lent to multiple students simultaneously.

Each student j (1 \leq j \leq N) has a "reading comprehension" T_j, and student j can only read books whose difficulty is at most T_j.

For each student, Takahashi selects and lends one book with the highest interestingness among the books that student can read. If there are multiple books with the highest interestingness, any of them may be chosen. Students who cannot read any books are not lent a book.

When books are lent to all students in this manner, find the total interestingness of the books that were lent out. For students who did not borrow a book, count their contribution as 0 in the total.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9
• 1 \leq R_i \leq 10^9
• 1 \leq T_j \leq 10^9
• All input values are integers

Sample Input 1

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

Sample Output 1

18

Sample Input 2

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

Sample Output 2

57

Sample Input 3

10 8
100 50
30 10
80 40
50 20
200 100
60 30
90 60
10 5
5 15 25 35 45 55 70 100 3 50

Sample Output 3

730

Problem Statement

Takahashi is a caretaker of a botanical garden. The botanical garden has N plants, numbered from 1 to N. These plants are managed in a tree structure, forming a rooted tree with plant 1 as the root.

For each plant i (2 \leq i \leq N), plant P_i is the parent of plant i.

Each plant has a value called moisture level, and the moisture level of every plant is initially 0.

Takahashi performs Q watering operations. In the j-th operation (1 \leq j \leq Q), he increases the moisture level of all plants in the subtree rooted at plant X_j by D_j. Here, the subtree rooted at plant X_j is the set consisting of plant X_j itself and all descendants of plant X_j.

Determine the moisture level of each plant after all Q watering operations have been performed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
• 1 \leq X_j \leq N (1 \leq j \leq Q)
• 1 \leq D_j \leq 10^9 (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

5 2
1 1 2 2
1 10
2 5

Sample Output 1

10 15 10 15 15

Sample Input 2

7 3
1 1 2 2 3 3
3 20
1 5
5 100

Sample Output 2

5 5 25 5 105 25 25

Sample Input 3

10 4
1 2 3 3 3 1 7 7 9
1 3
3 7
7 2
9 10

Sample Output 3

3 3 10 10 10 10 5 5 15 15

Problem Statement

Takahashi has been assigned the task of placing advertisement panels along a long corridor in an exhibition hall. The corridor is divided into slots every 1 meter, with a total length of L meters. That is, slots 1, 2, \ldots, L are lined up in a row.

Takahashi has N advertisement panels as candidates. All N advertisement panels are distinct, and he can independently choose whether or not to install each one. Each panel can be installed at most once, and if installed, it can be freely placed at any position along the corridor (as long as the constraints described below are satisfied). There are no constraints based on the order of placement or panel numbering.

The i-th advertisement panel (1 \leq i \leq N) occupies w_i consecutive slots. Specifically, if the i-th advertisement panel is installed with its left edge aligned to slot s, it occupies slots s, s+1, \ldots, s+w_i-1 (where 1 \leq s and s + w_i - 1 \leq L must hold). If the i-th advertisement panel is installed, it provides an attraction effect of b_i. Panels that are not installed provide no attraction effect.

Advertisement panels cannot overlap each other. That is, two different installed advertisement panels cannot occupy the same slot simultaneously. As long as they do not overlap, placing them adjacent to each other is acceptable.

Once the placement of the chosen advertisement panels is determined, any slot not occupied by any advertisement panel becomes a vacant slot. If no panels are installed, all slots are vacant slots.

This corridor has fire safety regulations. Emergency guidance lights are installed at regular intervals on the corridor walls, and in sections where vacant slots continue for a long stretch, there is a concern that visitors may not pay attention to the guidance lights. Therefore, the following fire safety regulation must be satisfied:

There must not be K or more consecutive vacant slots on the corridor. That is, the length of any maximal interval of consecutive vacant slots must be K-1 or less at every location.

This constraint also applies near both ends of the corridor. For example, if the left edge of the leftmost installed advertisement panel is at slot s, then slots 1 through s-1 are all vacant slots, forming s-1 consecutive vacant slots, so s - 1 \leq K - 1 must hold. Similarly, if the right edge of the rightmost installed advertisement panel is at slot t, then the L-t consecutive vacant slots from slot t+1 to slot L must also satisfy L - t \leq K - 1.

If no advertisement panels are installed, all L slots from slot 1 to slot L are consecutive vacant slots. Therefore, a placement with no panels installed satisfies the fire safety regulation only when L \leq K - 1 (i.e., L < K). In this case, the total attraction effect is 0.

Takahashi wants to maximize the total attraction effect of the installed advertisement panels while satisfying the fire safety regulation.

If there exists at least one way to select and place advertisement panels that satisfies the fire safety regulation, output the maximum total attraction effect. If no placement satisfying the fire safety regulation exists, output -1.

Constraints

• 1 \leq N \leq 400
• 1 \leq L \leq 1000
• 1 \leq K \leq L
• 1 \leq w_i \leq L (1 \leq i \leq N)
• 1 \leq b_i \leq 10^6 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

4 8 3
2 5
3 8
1 2
4 7

Sample Output 1

17

Sample Input 2

3 5 1
2 10
4 20
4 30

Sample Output 2

-1

Sample Input 3

12 30 5
3 12
7 25
4 14
6 18
2 7
5 16
8 30
1 3
9 28
4 13
10 35
6 20

Sample Output 3

109

Sample Input 4

30 100 7
5 120
12 260
7 150
20 500
3 60
15 330
8 180
10 210
6 140
25 620
4 90
18 410
9 200
11 240
13 290
2 45
16 370
14 310
7 170
5 115
22 540
19 430
1 20
30 750
6 135
10 230
17 390
8 175
24 580
12 255

Sample Output 4

2475

Sample Input 5

1 1 1
1 100

Sample Output 5

100

Problem Statement

Takahashi is the administrator of a corporate network consisting of N computers. Each computer is numbered from 1 to N.

It has been discovered that M types of computer viruses exist in this network. Each virus is numbered from 1 to M.

Virus j (1 \leq j \leq M) has the ability to infect a specific set of computers S_j. S_j may be empty.

Takahashi wants to mitigate the damage by dividing the N computers into several subnetworks (groups) and installing firewalls to block communication between groups. Here, a grouping means partitioning the set of N computers into one or more non-empty groups, where every computer belongs to exactly one group. The number of groups can be any number from 1 to N.

The damage from each virus is determined independently according to the following rules:

• If all computers in virus j's infection target S_j belong to the same group, virus j spreads within the group without being blocked by any firewall, and all computers in S_j are damaged.
• If the computers in virus j's infection target S_j are spread across two or more different groups, virus j's spread is blocked by the firewall, and no computer in S_j is damaged.

Here, if S_j is empty or contains only one computer, all computers in S_j are considered to belong to the same group. (If S_j is empty, no computer is damaged. If S_j contains only one computer, that computer is always damaged regardless of the grouping.)

Considering the damage from all M types of viruses, we want to minimize the number of computers that are damaged by one or more viruses (even if the same computer is damaged by multiple viruses, it is counted as one).

Find the minimum number of damaged computers when the optimal grouping is chosen.

Constraints

• 1 \leq N \leq 15
• 1 \leq M \leq 500
• 0 \leq k_j \leq N (1 \leq j \leq M)
• 1 \leq s_{j,i} \leq N (1 \leq j \leq M, 1 \leq i \leq k_j)
• The computer numbers s_{j,1}, s_{j,2}, \ldots, s_{j,k_j} in the infection target of virus j are all distinct
• All input values are integers

Sample Input 1

3 3
2 1 2
2 2 3
1 1

Sample Output 1

1

Sample Input 2

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

Sample Output 2

0

Sample Input 3

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

Sample Output 3

1

Sample Input 4

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

Sample Output 4

2

Sample Input 5

1 1
0

Sample Output 5

0