Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

• 1 \leq N, D \leq 2000
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4 5
2 -1
3 1
8 8
0 5

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

Takahashi is a cashier.

There is a cash register with 11 keys: 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The cash register initially displays 0. Whenever he types the key 00, the displayed number is multiplied by 100; whenever he types one of the others, the displayed number is multiplied by 10, and then added by the number written on the key.

Takahashi wants the cash register to display an integer S. At least how many keystrokes are required to make it display S?

Constraints

• 1\leq S\leq 10^{100000}
• S is an integer.

Sample Input 1

40004

Sample Output 1

4

For example, the following four keystrokes make the cash register display 40004. Initially, the cash register displays 0.

• Type the key 4. It now displays 4.
• Type the key 00. It now displays 400.
• Type the key 0. It now displays 4000.
• Type the key 4. It now displays 40004.

He cannot make it display 40004 with three or fewer keystrokes, so 4 should be printed.

Sample Input 2

1355506027

Sample Output 2

10

Sample Input 3

10888869450418352160768000001

Sample Output 3

27

Note that S may not fit into a 64-\operatorname{bit} integer type.

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

There are N items in a shop, numbered as Item 1, Item 2, \ldots, Item N.
For each i = 1, 2, \ldots, N, the regular price of Item i is A_i yen. For each item, there is only one in stock.

Takahashi wants M items: Item X_1, Item X_2, \ldots, Item X_M.

He repeats the following until he gets all items he wants.

Let r be the number of unsold items now. Choose an integer j such that 1 \leq j \leq r, and buy the item with the j-th smallest item number among the unsold items, for its regular price plus C_j yen.

Print the smallest total amount of money needed to get all items Takahashi wants.

Takahashi may also buy items other than the ones he wants.

Constraints

• 1 \leq M \leq N \leq 5000
• 1 \leq A_i \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq X_1 \lt X_2 \lt \cdots \lt X_M \leq N
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

17

Here is a way for Takahashi to get all items he wants with the smallest total amount of money.

• Initially, five items, Items 1, 2, 3, 4, 5, are remaining. Choose j = 5 to buy the item with the fifth smallest item number among the remaining, Item 5, for A_5 + C_5 = 5 + 3 = 8 yen.
• Then, four items, Items 1, 2, 3, 4, are remaining. Choose j = 2 to buy the item with the second smallest item number among the remaining, Item 2, for A_2 + C_2 = 1 + 2 = 3 yen.
• Then, three items, Items 1, 3, 4, are remaining. Choose j = 2 to buy the item with the second smallest item number among the remaining, Item 3, for A_3 + C_2 = 4 + 2 = 6 yen.

Now, Takahashi has all items he wants, Items 3 and 5, (along with Item 2, which is not wanted) for a total cost of 8 + 3 + 6 = 17 yen, the minimum possible.

Sample Input 2

20 8
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62
32 38 84 49 93 53 26 13 25 2 76 32 42 34 18 77 14 67 88 12
1 3 4 5 8 14 16 20

Sample Output 2

533

Problem Statement

There are integer sequences A, B, C of length M each.

C is represented by integers x_1, \dots, x_N, y_1, \dots, y_N. The first y_1 terms of C are x_1, the subsequent y_2 terms are x_2, \ldots, the last y_N terms are x_N.

B is defined by B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M).

A is defined by A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M).

Find the maximum value among A_1, \dots, A_M.

You will be given T test cases to solve.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• The sum of N in a single file is at most 2 \times 10^5.
• 1 \leq M \leq 10^9
• |x_i| \leq 4 \, (1 \leq i \leq N)
• y_i \gt 0 \, (1 \leq i \leq N)
• \sum_{k = 1}^N y_k = M
• All values in input are integers.

Sample Input 1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

Sample Output 1

4
53910
2000000002000000000

In the first test case, we have:

• C = (-1, -1, 2, 2, 2, -3, -3)
• B = (-1, -2, 0, 2, 4, 1, -2)
• A = (-1, -3, -3, -1, 3, 4, 2)

Thus, the maximum value among A_1, \dots, A_M is 4.