Problem Statement

There are N sellers and M buyers in an apple market.

The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).

The i-th buyer may buy an apple for B_i yen or less.

Find the minimum integer X that satisfies the following condition.

Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.

Constraints

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

Sample Input 1

3 4
110 90 120
100 80 120 10000

Sample Output 1

110

Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.

Since an integer less than 110 does not satisfy the condition, this is the answer.

Sample Input 2

5 2
100000 100000 100000 100000 100000
100 200

Sample Output 2

201

Sample Input 3

3 2
100 100 100
80 120

Sample Output 3

100

Problem Statement

You are given a string S of length N consisting of lowercase English letters, ,, and ". It is guaranteed that S contains an even number of ".

Let 2K be the number of " in S. For each i=1,2,\ldots,K, the characters from the (2i-1)-th " through the (2i)-th " are said to be enclosed.

Your task is to replace each , in S that is not an enclosed character with . and print the resulting string.

Constraints

• N is an integer between 1 and 2\times 10^5, inclusive.
• S is a string of length N consisting of lowercase English letters, ,, and ".
• S contains an even number of ".

Sample Input 1

8
"a,b"c,d

Sample Output 1

"a,b"c.d

In S, "a,b" are enclosed characters, and c,d are not.

The , in S that is not an enclosed character is the seventh character from the left in S, so replace that character with . to get the answer.

Sample Input 2

5
,,,,,

Sample Output 2

.....

Sample Input 3

20
a,"t,"c,"o,"d,"e,"r,

Sample Output 3

a."t,"c."o,"d."e,"r.

Problem Statement

You are given positive integers N and M.
Find the smallest positive integer X that satisfies both of the conditions below, or print -1 if there is no such integer.

• X can be represented as the product of two integers a and b between 1 and N, inclusive. Here, a and b may be the same.
• X is at least M.

Constraints

• 1\leq N\leq 10^{12}
• 1\leq M\leq 10^{12}
• N and M are integers.

Sample Input 1

5 7

Sample Output 1

8

First, 7 cannot be represented as the product of two integers between 1 and 5.
Second, 8 can be represented as the product of two integers between 1 and 5, such as 8=2\times 4.

Thus, you should print 8.

Sample Input 2

2 5

Sample Output 2

-1

Since 1\times 1=1, 1\times 2=2, 2\times 1=2, and 2\times 2=4, only 1, 2, and 4 can be represented as the product of two integers between 1 and 2, so no number greater than or equal to 5 can be represented as the product of two such integers.
Thus, you should print -1.

Sample Input 3

100000 10000000000

Sample Output 3

10000000000

For a=b=100000 (=10^5), the product of a and b is 10000000000 (=10^{10}), which is the answer.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

In the world where Takahashi lives, a week has N days.

Takahashi, the king of the Kingdom of AtCoder, assigns "weekday" or "holiday" to each day of week. The assignments should be the same for all weeks. At least one day of week should be assigned "holiday".

Under such conditions, the productivity of the i-th day of week is defined by a sequence A of length N as follows:

• if the i-th day of week is "holiday", its productivity is 0;
• if the i-th day of week is "weekday", its productivity is A_{\min(x,y)}, if the last holiday is x days before and the next one is y days after.
  • Note that the last/next holiday may belong to a different week due to the periodic assignments. For details, see the Samples.

Find the maximum productivity per week when the assignments are chosen optimally.
Here, the productivity per week refers to the sum of the productivities of the 1-st, 2-nd, \dots, and N-th day of week.

Constraints

• All values in the input are integers.
• 1 \le N \le 5000
• 1 \le A_i \le 10^9

Sample Input 1

7
10 10 1 1 1 1 1

Sample Output 1

50

For example, we can assign "holiday" to the 2-nd and 4-th day of week and "weekday" to the rest to achieve a productivity of 50 per week:

• the 1-st day of week ... x=4 and y=1, so its productivity is A_1 = 10.
• the 2-nd day of week ... it is holiday, so its productivity is 0.
• the 3-st day of week ... x=1 and y=1, so its productivity is A_1 = 10.
• the 4-th day of week ... it is holiday, so its productivity is 0.
• the 5-th day of week ... x=1 and y=4, so its productivity is A_1 = 10.
• the 6-th day of week ... x=2 and y=3, so its productivity is A_2 = 10.
• the 7-th day of week ... x=3 and y=2, so its productivity is A_2 = 10.

It is impossible to make the productivity per week 51 or greater.

Sample Input 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

Sample Output 2

5100000000

Sample Input 3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

Sample Output 3

236980

Problem Statement

Given are two sequences of N integers each: A = (A_1, A_2, \ldots, A_N) and B = (B_1, B_2 \ldots, B_N).

On the sequence A, you can do the two operations below any number of times (possibly zero) in any order.

• Choose an integer i satisfying 1 \leq i \leq N, and increase or decrease A_i by 1, for the cost of X yen (Japanese currency).
• Choose an integer i satisfying 1 \leq i \leq N-1, and swap the values of A_i and A_{i+1}, for the cost of Y yen.

Print the minimum total cost needed to make the sequence A equal the sequence B by repeating the above.

Constraints

• 2 \leq N \leq 18
• 1 \leq X \leq 10^8
• 1 \leq Y \leq 10^{16}
• 1 \leq A_i, B_i \leq 10^8
• All values in input are integers.

Sample Input 1

4 3 5
4 2 5 2
6 4 2 1

Sample Output 1

16

Initialy, we have A = (4, 2, 5, 2).
The following sequence of operations makes A equal B.

• Pay X = 3 yen to increase the value of A_3 by 1, making A = (4, 2, 6, 2).
• Pay Y = 5 yen to swap the values of A_2 and A_3, making A = (4, 6, 2, 2).
• Pay Y = 5 yen to swap the values of A_1 and A_2, making A = (6, 4, 2, 2).
• Pay X = 3 yen to decrease the value of A_4 by 1, making A = (6, 4, 2, 1).

The total cost of these operations is 3+5+5+3 = 16 yen, which is the minimum possible.

Sample Input 2

5 12345 6789
1 2 3 4 5
1 2 3 4 5

Sample Output 2

0

A and B are equal from the beginning, so no operation is needed.

Sample Input 3

18 20719114 5117250357733867
10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712
14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

Sample Output 3

13104119429316474

Note that values in input or output may not fit into 32-bit integer types.