Problem Statement

There is a mysterious button. When you press this button, you receive one candy, unless less than C seconds have elapsed since you last received a candy.

Takahashi decided to press this button N times. He will press the button for the i-th time T_i seconds from now.

How many candies will he receive?

Constraints

• 1 \leq N \leq 100
• 1 \leq C \leq 1000
• 0 \leq T_1 < T_2 < \dots < T_N \leq 1000
• All input values are integers.

Sample Input 1

6 5
1 3 7 8 10 12

Sample Output 1

3

Takahashi will press the button six times.

• 1st press (1 second from now): You always receive a candy when pressing the button for the first time.
• 2nd press (3 seconds from now): 3 - 1 = 2 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
• 3rd press (7 seconds from now): 7 - 1 = 6 \geq C seconds have elapsed since he last received a candy, so he receives a candy.
• 4th press (8 seconds from now): 8 - 7 = 1 < C second has elapsed since he last received a candy, so he does not receive a candy.
• 5th press (10 seconds from now): 10 - 7 = 3 < C seconds have elapsed since he last received a candy, so he does not receive a candy.
• 6th press (12 seconds from now): 12 - 7 = 5 \geq C seconds have elapsed since he last received a candy, so he receives a candy.

Therefore, he receives three candies.

Sample Input 2

3 2
0 2 4

Sample Output 2

3

Sample Input 3

10 3
0 3 4 6 9 12 15 17 19 20

Sample Output 3

7

Problem Statement

You are given a sequence of N integers: A=(A _ 1,A _ 2,\ldots,A _ N).

Print all even numbers in A without changing the order.

Constraints

• 1\leq N\leq 100
• 1\leq A _ i\leq 100\ (1\leq i\leq N)
• A contains at least one even number.
• All values in the input are integers.

Sample Input 1

5
1 2 3 5 6

Sample Output 1

2 6

We have A=(1,2,3,5,6). Among them are two even numbers, A _ 2=2 and A _ 5=6, so print 2 and 6 in this order, with a space in between.

Sample Input 2

5
2 2 2 3 3

Sample Output 2

2 2 2

A may contain equal elements.

Sample Input 3

10
22 3 17 8 30 15 12 14 11 17

Sample Output 3

22 8 30 12 14

Problem Statement

You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy; if it does, print Hard.

Constraints

• A and B are integers.
• 1 \le A,B \le 10^{18}

Sample Input 1

229 390

Sample Output 1

Hard

When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard.

Sample Input 2

123456789 9876543210

Sample Output 2

Easy

We do not have a carry here; the answer is Easy.
Note that the input may not fit into a 32-bit integer.

Problem Statement

There are N people numbered Person 1, Person 2, \dots, and Person N. Person i has a family name s_i and a given name t_i.

Consider giving a nickname to each of the N people. Person i's nickname a_i should satisfy all the conditions below.

• a_i coincides with Person i's family name or given name. In other words, a_i = s_i and/or a_i = t_i holds.
• a_i does not coincide with the family name and the given name of any other person. In other words, for all integer j such that 1 \leq j \leq N and i \neq j, it holds that a_i \neq s_j and a_i \neq t_j.

Is it possible to give nicknames to all the N people? If it is possible, print Yes; otherwise, print No.

Constraints

• 2 \leq N \leq 100
• N is an integer.
• s_i and t_i are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English alphabets.

Sample Input 1

3
tanaka taro
tanaka jiro
suzuki hanako

Sample Output 1

Yes

The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 = taro, a_2 = jiro, a_3 = hanako. (a_3 may be suzuki, too.)
However, note that we cannot let a_1 = tanaka, which violates the second condition of nicknames, since Person 2's family name s_2 is tanaka too.

Sample Input 2

3
aaa bbb
xxx aaa
bbb yyy

Sample Output 2

No

There is no way to give nicknames satisfying the conditions in the Problem Statement.

Sample Input 3

2
tanaka taro
tanaka taro

Sample Output 3

No

There may be a pair of people with the same family name and the same given name.

Sample Input 4

3
takahashi chokudai
aoki kensho
snu ke

Sample Output 4

Yes

We can let a_1 = chokudai, a_2 = kensho, and a_3 = ke.

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).

Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.

Print the minimum amount of money Takahashi needs to buy all the items.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K, X \leq 10^9
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

5 4 7
8 3 10 5 13

Sample Output 1

12

By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:

• buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
• buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
• buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
• buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
• buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,

for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.

Sample Input 2

5 100 7
8 3 10 5 13

Sample Output 2

0

Sample Input 3

20 815 60
2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202

Sample Output 3

112

Problem Statement

There are N products labeled 1 to N flowing on a conveyor belt. A Keyence printer is attached to the conveyor belt, and product i enters the range of the printer T_i microseconds from now and leaves it D_i microseconds later.

The Keyence printer can instantly print on one product within the range of the printer (in particular, it is possible to print at the moment the product enters or leaves the range of the printer). However, after printing once, it requires a charge time of 1 microseconds before it can print again. What is the maximum number of products the printer can print on when the product and timing for the printer to print are chosen optimally?

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq T_i,D_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5
1 1
1 1
2 1
1 2
1 4

Sample Output 1

4

Below, we will simply call the moment t microseconds from now time t.

For example, you can print on four products as follows:

• Time 1 : Products 1,2,4,5 enter the range of the printer. Print on product 4.
• Time 2 : Product 3 enters the range of the printer, and products 1,2 leave the range of the printer. Print on product 1.
• Time 3 : Products 3,4 leave the range of the printer. Print on product 3.
• Time 4.5 : Print on product 5.
• Time 5 : Product 5 leaves the range of the printer.

It is impossible to print on all five products, so the answer is 4.

Sample Input 2

2
1 1
1000000000000000000 1000000000000000000

Sample Output 2

2

Sample Input 3

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

Sample Output 3

6

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

Each square contains an integer. For each i = 1, 2, \ldots, N, the square (r_i, c_i) contains a positive integer a_i. The other square contains a 0.

Initially, there is a piece on the square (R, C). Takahashi can move the piece to a square other than the square it occupies now, any number of times. However, when moving the piece, both of the following conditions must be satisfied.

• The integer written on the square to which the piece is moved is strictly greater than the integer written on the square from which the piece is moved.
• The squares to and from which the piece is moved are in the same row or the same column.

For each i = 1, 2, \ldots, N, print the maximum number of times Takahashi can move the piece when (R, C) = (r_i, c_i).

Constraints

• 2 \leq H, W \leq 2 \times 10^5
• 1 \leq N \leq \min(2 \times 10^5, HW)
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• 1 \leq a_i \leq 10^9
• i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
0
2
0
3
1
0

The grid contains the following integers.

4 7 0
3 0 5
2 5 5

• When (R, C) = (r_1, c_1) = (1, 1), you can move the piece once by moving it as (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_2, c_2) = (1, 2), you cannot move the piece at all.
• When (R, C) = (r_3, c_3) = (2, 1), you can move the piece twice by moving it as (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_4, c_4) = (2, 3), you cannot move the piece at all.
• When (R, C) = (r_5, c_5) = (3, 1), you can move the piece three times by moving it as (3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_6, c_6) = (3, 2), you can move the piece once by moving it as (3, 2) \rightarrow (1, 2).
• When (R, C) = (r_7, c_7) = (3, 3), you cannot move the piece at all.

Sample Input 2

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

Sample Output 2

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

Problem Statement

You are given a simple undirected graph consisting of N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge connects vertices u_i and v_i. Also, for i = 1, 2, \ldots, N, vertex i is assigned a positive integer W_i, and there are A_i pieces placed on it.

As long as there are pieces on the graph, repeat the following operation:

• First, choose and remove one piece from the graph, and let x be the vertex on which the piece was placed.
• Choose a (possibly empty) set S of vertices adjacent to x such that \sum_{y \in S} W_y \lt W_x, and place one piece on each vertex in S.

Print the maximum number of times the operation can be performed.

It can be proved that, regardless of how the operation is performed, there will be no pieces on the graph after a finite number of iterations.

Constraints

• All input values are integers.
• 2 \leq N \leq 5000
• 1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
• 1 \leq W_i \leq 5000
• 0 \leq A_i \leq 10^9

Sample Input 1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

Sample Output 1

5

In the following explanation, let A = (A_1, A_2, \ldots, A_N) represent the numbers of pieces on the vertices. Initially, A = (1, 0, 0, 0, 0, 1).

Consider performing the operation as follows:

• Remove one piece from vertex 1 and place one piece each on vertices 2 and 3. Now, A = (0, 1, 1, 0, 0, 1).
• Remove one piece from vertex 2. Now, A = (0, 0, 1, 0, 0, 1).
• Remove one piece from vertex 6. Now, A = (0, 0, 1, 0, 0, 0).
• Remove one piece from vertex 3 and place one piece on vertex 2. Now, A = (0, 1, 0, 0, 0, 0).
• Remove one piece from vertex 2. Now, A = (0, 0, 0, 0, 0, 0).

In this procedure, the operation is performed five times, which is the maximum possible number of times.

Sample Input 2

2 1
1 2
1 2
0 0

Sample Output 2

0

In this sample input, there are no pieces on the graph from the beginning.

Sample Input 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1

Sample Output 3

1380