Problem Statement

There is one humidifier in the AtCoder company office. The current time is 0, and the humidifier has no water inside.

You will add water to this humidifier N times. The i-th addition of water (1 \leq i \leq N) takes place at time T_i, and you add V_i liters of water. It is guaranteed that T_i < T_{i+1} for all 1 \leq i \leq N-1.

However, the humidifier has a leak, and as long as there is water inside, the amount of water decreases by 1 liter per unit time.

Find the amount of water remaining in the humidifier immediately after you finish adding water at time T_N.

Constraints

• 1 \leq N \leq 100
• 1 \leq T_i \leq 100 (1 \leq i \leq N)
• 1 \leq V_i \leq 100 (1 \leq i \leq N)
• T_i < T_{i+1} (1 \leq i \leq N-1)
• All input values are integers.

Sample Input 1

4
1 3
3 1
4 4
7 1

Sample Output 1

3

At each point in time, water is added as follows:

• Time 1: Before adding, the humidifier has 0 liters. After adding 3 liters, it has 3 liters.
• Time 3: Before adding, it has 1 liter. After adding 1 liter, it has 2 liters total.
• Time 4: Before adding, it has 1 liter. After adding 4 liters, it has 5 liters total.
• Time 7: Before adding, it has 2 liters. After adding 1 liter, it has 3 liters total.

After finishing the addition at time 7, the humidifier contains 3 liters. Thus, the answer is 3.

Sample Input 2

3
1 8
10 11
21 5

Sample Output 2

5

Sample Input 3

10
2 1
22 10
26 17
29 2
45 20
47 32
72 12
75 1
81 31
97 7

Sample Output 3

57

Problem Statement

The AtCoder company office can be represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell contains a desk; if S_{i,j} is ., that cell is a floor. It is guaranteed that there are at least two floor cells.

You will choose two distinct floor cells and place a humidifier on each.

After placing the humidifiers, a cell (i,j) is humidified if and only if it is within a Manhattan distance D from at least one of the humidifier cells (i',j'). The Manhattan distance between (i,j) and (i',j') is defined as |i - i'| + |j - j'|. Note that any floor cell on which a humidifier is placed is always humidified.

Find the maximum possible number of humidified floor cells.

Constraints

• 1 \leq H \leq 10
• 1 \leq W \leq 10
• 2 \leq H \times W
• 0 \leq D \leq H+W-2
• H,W,D are integers.
• S_{i,j} is # or .. (1 \leq i \leq H, 1 \leq j \leq W)
• There are at least two floor cells.

Sample Input 1

2 5 1
.###.
.#.##

Sample Output 1

3

When placing humidifiers on (1,1) and (1,5):

• From the humidifier on (1,1), two cells (1,1) and (2,1) are humidified.
• From the humidifier on (1,5), one cell (1,5) is humidified.

In total, three cells are humidified. No configuration can humidify four or more floor cells, so the answer is 3.

Sample Input 2

5 5 2
.#.#.
.....
.#.#.
#.#.#
.....

Sample Output 2

15

When placing humidifiers on (2,4) and (5,3), 15 floor cells are humidified.

Sample Input 3

4 4 2
....
.##.
.##.
....

Sample Output 3

10

Problem Statement

The AtCoder company office is represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell has a wall; if S_{i,j} is ., that cell is a floor; if S_{i,j} is H, that cell has a humidifier placed on a floor cell.

A certain cell is considered humidified if it can be reached from at least one humidifier cell by at most D moves up, down, left, or right without passing through a wall. Note that any cell with a humidifier is always humidified.

Find the number of humidified floor cells.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• 0 \leq D \leq H\times W
• S_{i,j} is #, ., or H. (1 \leq i \leq H, 1 \leq j \leq W)
• All input numbers are integers.

Sample Input 1

3 4 1
H...
#..H
.#.#

Sample Output 1

5

Five cells (1,1), (1,2), (1,4), (2,3), (2,4) are humidified.

Sample Input 2

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

Sample Output 2

21

Sample Input 3

1 6 3
...#..

Sample Output 3

0

It is possible that no cells are humidified.

Problem Statement

Find the number of positive integers not greater than N that have exactly 9 positive divisors.

Constraints

• 1 \leq N \leq 4 \times 10^{12}
• All input values are integers.

Sample Input 1

200

Sample Output 1

3

Three positive integers 36,100,196 satisfy the condition.

Sample Input 2

4000000000000

Sample Output 2

407073

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N and edges are numbered 1 to M. Edge i (1 \leq i \leq M) connects vertices u_i and v_i bidirectionally and has weight w_i.

For a path, define its weight as the maximum weight of an edge in the path. Define f(x, y) as the minimum possible path weight of a path from vertex x to vertex y.

You are given two sequences of length K: (A_1, A_2, \ldots, A_K) and (B_1, B_2, \ldots, B_K). It is guaranteed that A_i \neq B_j (1 \leq i,j \leq K).

Permute the sequence B freely so that \displaystyle \sum_{i=1}^{K} f(A_i, B_i) is minimized.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq \min(\frac{N \times (N-1)}{2},2 \times 10^5)
• 1 \leq K \leq N
• 1 \leq u_i<v_i \leq N (1 \leq i \leq M)
• 1 \leq w_i \leq 10^9
• 1 \leq A_i,B_i \leq N (1 \leq i \leq K)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

8

If we rearrange B as (2,4,4):

• f(1,2) = 5: The path from vertex 1 to vertex 2 passing through vertex 4 contains edge 3 with a maximum edge weight of 5. There is no path with a maximum edge weight less than or equal to 4, so 5 is the minimum possible.
• f(1,4) = 2: The path from vertex 1 to vertex 4 passing through vertex 3 contains edge 1 with a maximum edge weight of 2. There is no path with a maximum edge weight less than or equal to 1, so 2 is the minimum possible.
• f(3,4) = 1: The path from vertex 3 to vertex 4 passing through the direct edge contains an edge with a maximum edge weight of 1. No path can have a maximum weight 0 or less, so 1 is the minimum possible.

Thus, \displaystyle \sum_{i=1}^{3} f(A_i, B_i) = 5+2+1=8. No permutation of B yields 7 or less, so the answer is 8.

Sample Input 2

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

Sample Output 2

3

Problem Statement

There are N products for sale in a store. The i-th product has a price of P_i yen, a utility value of U_i, and a color C_i.

You will choose some subset of these N products to buy (possibly none). The total price of the chosen products must be at most X yen.

Your satisfaction is S + T \times K, where S is the sum of utilities of the chosen products, and T is the number of distinct colors among the chosen products. Here, K is a given constant.

You will choose products to maximize your satisfaction. Find the maximized satisfaction.

Constraints

• 1 \leq N \leq 500
• 1 \leq X \leq 50000
• 1 \leq K \leq 10^9
• 1 \leq P_i \leq X (1 \leq i \leq N)
• 1 \leq U_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq C_i \leq N (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

17

If you buy the 1st and 2nd products, the total utility S is 7, and the number of distinct colors T is 2. Thus, your satisfaction is 7 + 2 \times 5 = 17. No purchase plan makes your satisfaction 18 or greater, so the answer is 17.

Sample Input 2

5 30 3
5 4 3
11 20 1
9 10 4
7 5 2
16 15 4

Sample Output 2

44

If you buy the 2nd, 3rd, and 4th products, the total utility S is 35, and the number of distinct colors T is 3. Thus, your satisfaction is 35 + 3 \times 3 = 44. No purchase plan makes your satisfaction 45 or greater, so the answer is 44.

Sample Input 3

22 75 6426
9 309 9
5 470 5
17 481 12
27 352 14
1 191 18
7 353 20
9 99 15
20 401 17
46 434 19
11 459 22
10 317 19
15 440 18
17 438 19
25 461 22
5 320 22
1 476 21
11 315 3
8 112 9
11 438 13
19 362 8
10 422 13
10 152 21

Sample Output 3

67717

Problem Statement

You have a row of N cells. The i-th cell from the left contains an integer A_i.

You also have \lfloor \frac{N}{K} \rfloor tiles, each of which covers K consecutive cells.

For each i = 1, \ldots, \lfloor \frac{N}{K} \rfloor, solve the following problem:

• When placing exactly i tiles without overlap, find the maximum possible sum of the numbers in the covered cells.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq \min(5,N)
• -10^9 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

6 2
-5 3 4 -1 6 -2

Sample Output 1

7 12 5

For i=1, if you cover the 2nd and 3rd cells with one tile, the sum of the numbers in the covered cells is 7.

For i=2, if you cover the 2nd and 3rd cells with one tile and the 4th and 5th cells with another tile, the sum of the numbers in the covered cells is 12.

Sample Input 2

20 4
-5 3 4 -1 6 -2 13 -1 13 7 6 -12 3 -5 12 -6 -3 10 -15 -5

Sample Output 2

32 45 57 52 22