Problem Statement

Takahashi threw three dice, and they showed three numbers a, b, and c.

If there are two same numbers among a, b, and c, print the remaining number. Otherwise, print 0.

Constraints

• 1 \leq a,b,c \leq 6
• All of a, b, and c are integers.

Sample Input 1

2 5 2

Sample Output 1

5

The first and third dice both showed 2, so we should print the number on the remaining dice, which is 5.

Sample Input 2

4 5 6

Sample Output 2

0

Any two numbers are different, so we should print 0.

Sample Input 3

1 1 1

Sample Output 3

1

Any two numbers are the same. Whichever two dice we choose, the number on the remaining dice will be 1.

Problem Statement

A condominium AtCoder has N floors, called the 1-st floor through the N-th floor. Each floor has K rooms, called the 1-st room through the K-th room.

Here, both N and K are one-digit integers, and the j-th room on the i-th floor has the room number i0j. For example, the 2-nd room on the 1-st floor has the room number 102.

Takahashi, the manager, got interested in the sum of the room numbers of all rooms in the condominium, where each room number is seen as a three-digit integer. Find this sum.

Constraints

• 1 \leq N,K \leq 9
• N and K are integers.

Sample Input 1

1 2

Sample Output 1

203

The condominium has two rooms 101 and 102. We have 101+102=203.

Sample Input 2

3 3

Sample Output 2

1818

Problem Statement

There are 10^{100}+1 villages, labeled with numbers 0, 1, \ldots, 10^{100}.
For every integer i between 0 and 10^{100}-1 (inclusive), you can pay 1 yen (the currency) in Village i to get to Village (i + 1). There is no other way to travel between villages.

Taro has K yen and is in Village 0 now. He will try to get to a village labeled with as large a number as possible.
He has N friends. The i-th friend, who is in Village A_i, will give Taro B_i yen when he reaches Village A_i.
Find the number with which the last village he will reach is labeled.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 10^{18}
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
2 1
5 10

Sample Output 1

4

Takahashi will travel as follows:

• Go from Village 0 to Village 1, for 1 yen. Now he has 2 yen.
• Go from Village 1 to Village 2, for 1 yen. Now he has 1 yen.
• Get 1 yen from the 1-st friend in Village 2. Now he has 2 yen.
• Go from Village 2 to Village 3, for 1 yen. Now he has 1 yen.
• Go from Village 3 to Village 4, for 1 yen. Now he has 0 yen, and he has no friends in this village, so his journey ends here.

Thus, we should print 4.

Sample Input 2

5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000

Sample Output 2

6000000000

Note that the answer may not fit into a 32-bit integer.

Sample Input 3

3 2
5 5
2 1
2 2

Sample Output 3

10

He may have multiple friends in the same village.

Problem Statement

The land of a park AtCoder is an N\times N grid with east-west rows and north-south columns. The height of the square at the i-th row from the north and j-th column from the west is given as A_{i,j}.

Takahashi, the manager, has decided to build a square pond occupying K \times K squares in this park.

To do this, he wants to choose a square section of K \times K squares completely within the park whose median of the heights of the squares is the lowest. Find the median of the heights of the squares in such a section.

Here, the median of the heights of the squares in a K \times K section is the height of the (\left\lfloor\frac{K^2}{2}\right\rfloor +1)-th highest square among the K^2 squares in the section, where \lfloor x\rfloor is the greatest integer not exceeding x.

Constraints

• 1 \leq K \leq N \leq 800
• 0 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

3 2
1 7 0
5 8 11
10 4 2

Sample Output 1

4

Let (i,j) denote the square at the i-th row from the north and j-th column from the west. We have four candidates for the 2 \times 2 section occupied by the pond: \{(1,1),(1,2),(2,1),(2,2)\}, \{(1,2),(1,3),(2,2),(2,3)\}, \{(2,1),(2,2),(3,1),(3,2)\}, \{(2,2),(2,3),(3,2),(3,3)\}.
When K=2, since \left\lfloor\frac{2^2}{2}\right\rfloor+1=3, the median of the heights of the squares in a section is the height of the 3-rd highest square, which is 5, 7, 5, 4 for the candidates above, respectively. We should print the lowest of these: 4.

Sample Input 2

3 3
1 2 3
4 5 6
7 8 9

Sample Output 2

5

Problem Statement

Let N be a positive integer. We have a (2N+1)\times (2N+1) grid where rows are numbered 0 through 2N and columns are also numbered 0 through 2N. Let (i,j) denote the square at Row i and Column j.

We have one white pawn, which is initially at (0, N). Also, we have M black pawns, the i-th of which is at (X_i, Y_i).

When the white pawn is at (i, j), you can do one of the following operations to move it:

• If 0\leq i\leq 2N-1, 0 \leq j\leq 2N hold and (i+1,j) does not contain a black pawn, move the white pawn to (i+1, j).
• If 0\leq i\leq 2N-1, 0 \leq j\leq 2N-1 hold and (i+1,j+1) does contain a black pawn, move the white pawn to (i+1,j+1).
• If 0\leq i\leq 2N-1, 1 \leq j\leq 2N hold and (i+1,j-1) does contain a black pawn, move the white pawn to (i+1,j-1).

You cannot move the black pawns.

Find the number of integers Y such that it is possible to have the white pawn at (2N, Y) by repeating these operations.

Constraints

• 1 \leq N \leq 10^9
• 0 \leq M \leq 2\times 10^5
• 1 \leq X_i \leq 2N
• 0 \leq Y_i \leq 2N
• (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

2 4
1 1
1 2
2 0
4 2

Sample Output 1

3

We can move the white pawn to (4,0), (4,1), and (4,2), as follows:

• (0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,2)
• (0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,1)
• (0,2)\to (1,1)\to (2,0)\to (3,0)\to (4,0)

On the other hand, we cannot move it to (4,3) or (4,4). Thus, we should print 3.

Sample Input 2

1 1
1 1

Sample Output 2

0

We cannot move the white pawn from (0,1).

Problem Statement

Takahashi's and Aoki's garden is covered with N weeds, called Weed 1, Weed 2, \ldots, Weed N. The height of Weed i is A_i. Takahashi and Aoki have decided to pull these weeds, as follows:

• First, Aoki will choose at most K weeds and pull them.
• Then, Takahashi will repeat the following operation until all weeds are pulled.
  • Let H be the height of the tallest remaining weeds. Pull all weeds with heights above \frac{H}{2} at once.

Aoki wants to minimize the number of operations done by Takahashi. Also, he wants to minimize it by pulling the minimum number of weeds needed. Find the number of operations done by Takahashi and the number of weeds Aoki pulls in this case.

Constraints

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

Sample Input 1

4 1
2 3 4 9

Sample Output 1

2 1

For example, assume that Aoki chooses Weed 4, with height 9, and pulls it. Then, the tallest remaining weed is Weed 3, with height 4. We have \frac{4}{2}=2, and Takahashi will pull Weed 2 and 3 in the first operation, since 2<3 and 2<4. Then, he will pull Weed 1 in the second operation, completing his work in two operations. On the other hand, he will not complete his work in one operation, no matter which one weed Aoki chooses.

Also, if Aoki pulls no weed, Takahashi will have to do three operations, so Aoki must pull at least one weed to minimize the number of operations done by Takahashi.

Sample Input 2

3 3
2 3 5

Sample Output 2

0 3

If Aoki pulls all weeds, Takahashi has to do zero operations, which is obviously the smallest number possible.

Sample Input 3

9 8
137 55 56 60 27 28 133 56 55

Sample Output 3

1 4