Problem Statement

You are given a positive integer N.

Find the maximum value of a palindromic cube number not greater than N.

Here, a positive integer K is defined to be a palindromic cube number if and only if it satisfies the following two conditions:

• There is a positive integer x such that x^3 = K.
• The decimal representation of K without leading zeros is a palindrome. More precisely, if K is represented as K = \sum_{i = 0}^{L-1} A_i10^i using integers A_0, A_1, \ldots, A_{L-2} between 0 and 9, inclusive, and an integer A_{L-1} between 1 and 9, inclusive, then A_i = A_{L-1-i} for all i = 0, 1, \ldots, L-1.

Constraints

• N is a positive integer not greater than 10^{18}.

Sample Input 1

345

Sample Output 1

343

343 is a palindromic cube number, while 344 and 345 are not. Thus, the answer is 343.

Sample Input 2

6

Sample Output 2

1

Sample Input 3

123456789012345

Sample Output 3

1334996994331

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 trampolines on a two-dimensional planar town where Takahashi lives. The i-th trampoline is located at the point (x_i, y_i) and has a power of P_i. Takahashi's jumping ability is denoted by S. Initially, S=0. Every time Takahashi trains, S increases by 1.

Takahashi can jump from the i-th to the j-th trampoline if and only if:

• P_iS\geq |x_i - x_j| +|y_i - y_j|.

Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.

At least how many times does he need to train to achieve his objective?

Constraints

• 2 \leq N \leq 200
• -10^9 \leq x_i,y_i \leq 10^9
• 1 \leq P_i \leq 10^9
• (x_i, y_i) \neq (x_j,y_j)\ (i\neq j)
• All values in input are integers.

Sample Input 1

4
-10 0 1
0 0 5
10 0 1
11 0 1

Sample Output 1

2

If he trains twice, S=2, in which case he can reach any trampoline from the 2-nd one.

For example, he can reach the 4-th trampoline as follows.

• Jump from the 2-nd to the 3-rd trampoline. (Since P_2 S = 10 and |x_2-x_3| + |y_2-y_3| = 10, it holds that P_2 S \geq |x_2-x_3| + |y_2-y_3|.)

• Jump from the 3-rd to the 4-th trampoline. (Since P_3 S = 2 and |x_3-x_4| + |y_3-y_4| = 1, it holds that P_3 S \geq |x_3-x_4| + |y_3-y_4|.)

Sample Input 2

7
20 31 1
13 4 3
-10 -15 2
34 26 5
-2 39 4
0 -50 1
5 -20 2

Sample Output 2

18

Problem Statement

AtCoder cafeteria sells meals consisting of a main dish and a side dish.
There are N types of main dishes, called main dish 1, main dish 2, \dots, main dish N. Main dish i costs a_i yen.
There are M types of side dishes, called side dish 1, side dish 2, \dots, side dish M. Side dish i costs b_i yen.

A set meal is composed by choosing one main dish and one side dish. The price of a set meal is the sum of the prices of the chosen main dish and side dish.
However, for L distinct pairs (c_1, d_1), \dots, (c_L, d_L), the set meal consisting of main dish c_i and side dish d_i is not offered because they do not go well together.
That is, NM - L set meals are offered. (The constraints guarantee that at least one set meal is offered.)

Find the price of the most expensive set meal offered.

Constraints

• 1 \leq N, M \leq 10^5
• 0 \leq L \leq \min(10^5, NM - 1)
• 1 \leq a_i, b_i \leq 10^9
• 1 \leq c_i \leq N
• 1 \leq d_j \leq M
• (c_i, d_i) \neq (c_j, d_j) if i \neq j.
• All input values are integers.

Sample Input 1

2 3 3
2 1
10 30 20
1 2
2 1
2 3

Sample Output 1

31

They offer three set meals, listed below, along with their prices:

• A set meal consisting of main dish 1 and side dish 1, at a price of 2 + 10 = 12 yen.
• A set meal consisting of main dish 1 and side dish 3, at a price of 2 + 20 = 22 yen.
• A set meal consisting of main dish 2 and side dish 2, at a price of 1 + 30 = 31 yen.

Among them, the most expensive is the third one. Thus, print 31.

Sample Input 2

2 1 0
1000000000 1
1000000000

Sample Output 2

2000000000

Sample Input 3

10 10 10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127
7017 46004 16086 62644 74928 57404 32168 45794 19493 71590
1 3
2 6
4 5
5 4
5 5
5 6
5 7
5 8
5 10
7 3

Sample Output 3

149076

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