Problem Statement

Takahashi is heading to AtCoder Land. There is a signboard in front of him, and he wants to determine whether it says AtCoder Land.

You are given two strings S and T separated by a space. Determine whether S= AtCoder and T= Land.

Constraints

• S and T are strings consisting of uppercase and lowercase English letters, with lengths between 1 and 10, inclusive.

Sample Input 1

AtCoder Land

Sample Output 1

Yes

S= AtCoder and T= Land.

Sample Input 2

CodeQUEEN Land

Sample Output 2

No

S is not AtCoder.

Sample Input 3

aTcodeR lANd

Sample Output 3

No

Uppercase and lowercase letters are distinguished.

Problem Statement

AtCoder Beginner Contest usually starts at 21:00 JST and lasts for 100 minutes.

You are given an integer K between 0 and 100 (inclusive). Print the time K minutes after 21:00 in the HH:MM format, where HH denotes the hour on the 24-hour clock and MM denotes the minute. If the hour or the minute has just one digit, append a 0 to the beginning to represent it as a 2-digit integer.

Constraints

• K is an integer between 0 and 100 (inclusive).

Sample Input 1

63

Sample Output 1

22:03

63 minutes after 21:00, it will be 22:03, so 22:03 should be printed.

The following outputs would be judged incorrect:

• 10:03
• 22:3

Sample Input 2

45

Sample Output 2

21:45

Sample Input 3

100

Sample Output 3

22:40

Problem Statement

There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,

• if the i-th character of S is o, the contestant ranked i-th in the qualification wants to participate in the final;
• if the i-th character of S is x, the contestant ranked i-th in the qualification does not want to participate in the final.

Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.

Print a string T of length N that satisfies the following conditions:

• if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is o;
• if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is x.

Constraints

• N and K are integers.
• 1 \le K \le N \le 100
• S is a string of length N consisting of o and x.
• S has at least K o's.

Sample Input 1

10 3
oxxoxooxox

Sample Output 1

oxxoxoxxxx

In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.

• The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
• The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
• The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
• The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
• The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
• Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.

Problem Statement

There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:

• if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.

A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)

You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.

Constraints

• 2 \leq N \leq 50
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
• There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.

Sample Input 2

3 2
1 3
2 3

Sample Output 2

-1

Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.

Sample Input 3

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

Sample Output 3

-1

Problem Statement

There are N giants, named 1 to N. When giant i stands on the ground, their shoulder height is A_i, and their head height is B_i.

You can choose a permutation (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and stack the N giants according to the following rules:

• First, place giant P_1 on the ground. The giant P_1's shoulder will be at a height of A_{P_1} from the ground, and their head will be at a height of B_{P_1} from the ground.

• For i = 1, 2, \ldots, N - 1 in order, place giant P_{i + 1} on the shoulders of giant P_i. If giant P_i's shoulders are at a height of t from the ground, then giant P_{i + 1}'s shoulders will be at a height of t + A_{P_{i + 1}} from the ground, and their head will be at a height of t + B_{P_{i + 1}} from the ground.

Find the maximum possible height of the head of the topmost giant P_N from the ground.

Constraints

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

Sample Input 1

3
4 10
5 8
2 9

Sample Output 1

18

If (P_1, P_2, P_3) = (2, 1, 3), then measuring from the ground, giant 2 has a shoulder height of 5 and a head height of 8, giant 1 has a shoulder height of 9 and a head height of 15, and giant 3 has a shoulder height of 11 and a head height of 18.

The head height of the topmost giant from the ground cannot be greater than 18, so print 18.

Sample Input 2

5
1 1
1 1
1 1
1 1
1 1

Sample Output 2

5

Sample Input 3

10
690830957 868532399
741145463 930111470
612846445 948344128
540375785 925723427
723092548 925021315
928915367 973970164
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

Sample Output 3

7362669937