Problem Statement

N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.

The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.

Constraints

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

Sample Input 1

6
1 123 12345 12 1234 123456

Sample Output 1

3

It is Player 3 who ranks fifth among the six players.

Sample Input 2

5
3 1 4 15 9

Sample Output 2

5

Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

• The string contains an uppercase English alphabet.
• The string contains a lowercase English alphabet.
• All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of uppercase and lowercase English alphabets.

Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.

Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.

Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.

Problem Statement

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were N submissions to POJ. In the i-th earliest submission, string S_i was submitted, and a score of T_i was given. (The same string may have been submitted multiple times.)
Note that POJ may not necessarily give the same score to submissions with the same string.

A submission is said to be an original submission if the string in the submission is never submitted in any earlier submission.
A submission is said to be the best submission if it is an original submission with the highest score. If there are multiple such submissions, only the earliest one is considered the best submission.

Find the index of the best submission.

Constraints

• 1 \leq N \leq 10^5
• S_i is a string consisting of lowercase English characters.
• S_i has a length between 1 and 10, inclusive.
• 0 \leq T_i \leq 10^9
• N and T_i are integers.

Sample Input 1

3
aaa 10
bbb 20
aaa 30

Sample Output 1

2

We will refer to the i-th earliest submission as Submission i.
Original submissions are Submissions 1 and 2. Submission 3 is not original because it has the same string as that in Submission 1.
Among the original submissions, Submission 2 has the highest score. Therefore, this is the best submission.

Sample Input 2

5
aaa 9
bbb 10
ccc 10
ddd 10
bbb 11

Sample Output 2

2

Original submissions are Submissions 1, 2, 3, and 4.
Among them, Submissions 2, 3, and 4 have the highest scores. In this case, the earliest submission among them, Submission 2, is the best.
As in this sample, beware that if multiple original submissions have the highest scores, only the one with the earliest among them is considered the best submission.

Sample Input 3

10
bb 3
ba 1
aa 4
bb 1
ba 5
aa 9
aa 2
ab 6
bb 5
ab 3

Sample Output 3

8

Problem Statement

Takahashi is displaying a sentence with N words in a window. All words have the same height, and the width of the i-th word (1\leq i\leq N) is L _ i.

The words are displayed in the window separated by a space of width 1. More precisely, when the sentence is displayed in a window of width W, the following conditions are satisfied.

• The sentence is divided into several lines.
• The first word is displayed at the beginning of the top line.
• The i-th word (2\leq i\leq N) is displayed either with a gap of 1 after the (i-1)-th word, or at the beginning of the line below the line containing the (i-1)-th word. It will not be displayed anywhere else.
• The width of each line does not exceed W. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.

When Takahashi displayed the sentence in the window, the sentence fit into M or fewer lines. Find the minimum possible width of the window.

Constraints

• 1\leq M\leq N\leq2\times10 ^ 5
• 1\leq L _ i\leq10^9\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

13 3
9 5 2 7 1 8 8 2 1 5 2 3 6

Sample Output 1

26

When the width of the window is 26, you can fit the given sentence into three lines as follows.

You cannot fit the given sentence into three lines when the width of the window is 25 or less, so print 26.

Note that you should not display a word across multiple lines, let the width of a line exceed the width of the window, or rearrange the words.

Sample Input 2

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

10000000009

Note that the answer may not fit into a 32\operatorname{bit} integer.

Sample Input 3

30 8
8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60

Sample Output 3

189