Problem Statement

As KEYENCE headquarters have more and more workers, they decided to divide the departments in the headquarters into two groups and stagger their lunch breaks.

KEYENCE headquarters have N departments, and the number of people in the i-th department (1\leq i\leq N) is K_i.

When assigning each department to Group A or Group B, having each group take lunch breaks at the same time, and ensuring that the lunch break times of Group A and Group B do not overlap, find the minimum possible value of the maximum number of people taking a lunch break at the same time.
In other words, find the minimum possible value of the larger of the following: the total number of people in departments assigned to Group A, and the total number of people in departments assigned to Group B.

Constraints

• 2 \leq N \leq 20
• 1 \leq K_i \leq 10^8
• All input values are integers.

Sample Input 1

5
2 3 5 10 12

Sample Output 1

17

When assigning departments 1, 2, and 5 to Group A, and departments 3 and 4 to Group B, Group A has a total of 2+3+12=17 people, and Group B has a total of 5+10=15 people. Thus, the maximum number of people taking a lunch break at the same time is 17.

It is impossible to assign the departments so that both groups have 16 or fewer people, so print 17.

Sample Input 2

2
1 1

Sample Output 2

1

Multiple departments may have the same number of people.

Sample Input 3

6
22 25 26 45 22 31

Sample Output 3

89

For example, when assigning departments 1, 4, and 5 to Group A, and departments 2, 3, and 6 to Group B, the maximum number of people taking a lunch break at the same time is 89.

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

A shop sells N kinds of lunchboxes, one for each kind.
For each i = 1, 2, \ldots, N, the i-th kind of lunchbox contains A_i takoyaki (octopus balls) and B_i taiyaki (fish-shaped cakes).

Takahashi wants to eat X or more takoyaki and Y or more taiyaki.
Determine whether it is possible to buy some number of lunchboxes to get at least X takoyaki and at least Y taiyaki. If it is possible, find the minimum number of lunchboxes that Takahashi must buy to get them.

Note that just one lunchbox is in stock for each kind; you cannot buy two or more lunchboxes of the same kind.

Constraints

• 1 \leq N \leq 300
• 1 \leq X, Y \leq 300
• 1 \leq A_i, B_i \leq 300
• All values in input are integers.

Sample Input 1

3
5 6
2 1
3 4
2 3

Sample Output 1

2

He wants to eat 5 or more takoyaki and 6 or more taiyaki.
Buying the second and third lunchboxes will get him 3 + 2 = 5 taiyaki and 4 + 3 = 7 taiyaki.

Sample Input 2

3
8 8
3 4
2 3
2 1

Sample Output 2

-1

Even if he is to buy every lunchbox, it is impossible to get at least 8 takoyaki and at least 8 taiyaki.
Thus, print -1.

Problem Statement

You are given an integer M and N pairs of integers (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N).
For all i, it holds that 1 \leq A_i \lt B_i \leq M.

A sequence S is said to be a good sequence if the following conditions are satisfied:

• S is a contiguous subsequence of the sequence (1,2,3,..., M).
• For all i, S contains at least one of A_i and B_i.

Let f(k) be the number of possible good sequences of length k.
Enumerate f(1), f(2), \dots, f(M).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq M
• All values in input are integers.

Sample Input 1

3 5
1 3
1 4
2 5

Sample Output 1

0 1 3 2 1

Here is the list of all possible good sequences.

• (1,2)
• (1,2,3)
• (2,3,4)
• (3,4,5)
• (1,2,3,4)
• (2,3,4,5)
• (1,2,3,4,5)

Sample Input 2

1 2
1 2

Sample Output 2

2 1

Sample Input 3

5 9
1 5
1 7
5 6
5 8
2 6

Sample Output 3

0 0 1 2 4 4 3 2 1

Problem Statement

There are N points labeled 1, 2, \dots, N on the xy-plane. Point i is located at coordinates (X_i, Y_i).
You can perform the following operation between 0 and K times, inclusive.

• First, choose one of the N points. Let k be the selected point, and assume it is currently at (x, y).
• Next, choose and execute one of the following four actions:
  • Move point k along the x-axis by +1. The coordinates of point k become (x+1, y).
  • Move point k along the x-axis by -1. The coordinates of point k become (x-1, y).
  • Move point k along the y-axis by +1. The coordinates of point k become (x, y+1).
  • Move point k along the y-axis by -1. The coordinates of point k become (x, y-1).
• It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates.

After all your operations, draw one square that includes all the N points inside or on the circumference, with each side parallel to the x- or y-axis.
Find the minimum possible value for the length of a side of this square. This value can be shown to be an integer since all points are always on lattice points.

In particular, if all points can be made to exist at the same coordinates, the answer is considered to be 0.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 0 \le K \le 4 \times 10^{14}
• 0 \le X_i, Y_i \le 10^9

Sample Input 1

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

Sample Output 1

3

The figure below illustrates this case with the horizontal x-axis and the vertical y-axis.

For example, after performing four moves following the arrows in the figure, you can include all points inside or on the circumference of the square shown in the figure with a side length of 3, and this can be shown to be the minimum value.

Sample Input 2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0

All points already exist at the same coordinates from the beginning.
For example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is 0.

Sample Input 3

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

Sample Output 3

484373824