Problem Statement

Takahashi is examining the record of wins and losses from his past N matches. The result of each match is recorded as either W representing a "win" or L representing a "loss".

Takahashi wants to know the longest streak of consecutive wins in this record.

Given the number of matches N and a string S of length N representing the wins and losses, find the length of the longest consecutive sequence of W in S. If S contains no W at all, the answer is 0.

Constraints

• 1 \leq N \leq 10^6
• S is a string of length N consisting only of W and L.

Sample Input 1

8
WLWWWLLW

Sample Output 1

3

Sample Input 2

5
LLLLL

Sample Output 2

0

Sample Input 3

20
WWLLWWWWWLWLWWWLLLWW

Sample Output 3

5

Sample Input 4

60
LWWWWLWWWLLWWWWWWLWLWWWWLWWLLLLWWWWWWWLWLWWWWWWWWLLLWWLWWWWW

Sample Output 4

8

Sample Input 5

1
W

Sample Output 5

1

Problem Statement

Takahashi is the manager of a soccer team. The team has N players, and each player is assigned exactly one jersey number from 1 to N. Takahashi must select K players from among them as regular members.

Each player i (1 \leq i \leq N) has two parameters: a practice evaluation score A_i and a recent match evaluation score B_i. The "overall evaluation" of player i is calculated as A_i + B_i.

Takahashi ranks all N players from rank 1 to rank N according to the following rules:

• A player with a higher overall evaluation is ranked higher (i.e., has a smaller rank value).
• Among players with equal overall evaluations, the player with the smaller jersey number is ranked higher.

Since jersey numbers are distinct for each player, these rules uniquely determine the rank of every player.

The K players ranked from 1st to Kth are selected as regular members.

Output the jersey numbers of the K players selected as regular members in ascending order.

Constraints

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

Sample Input 1

5 3
10 20
30 10
20 20
15 25
25 15

Sample Output 1

2
3
4

Sample Input 2

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

Sample Output 2

1
2
3

Sample Input 3

10 4
50 60
80 30
45 55
70 40
60 50
90 20
30 80
100 10
55 45
65 35

Sample Output 3

1
2
4
5

Sample Input 4

20 7
500 300
100 900
350 350
700 200
450 550
600 400
250 750
800 100
150 850
400 500
550 450
300 600
650 250
200 800
750 150
50 950
900 50
1000 1
1 1000
500 500

Sample Output 4

2
5
6
7
9
18
19

Sample Input 5

1 1
1 1

Sample Output 5

1

Problem Statement

Takahashi, as the manager of his part-time workplace, is trying to assign this month's M shift slots to N staff members.

Each staff member i (1 \leq i \leq N) has a predetermined maximum number of slots R_i they can work this month. Takahashi determines the number of slots X_i assigned to each staff member as a non-negative integer satisfying 0 \leq X_i \leq R_i.

The assignment must satisfy the following total condition:

• Total condition: The total number of assigned shifts is exactly M slots. That is, X_1 + X_2 + \cdots + X_N = M.

When at least one assignment satisfying the total condition exists, Takahashi wants to minimize the unfairness. Here, for each staff member i, the difference R_i - X_i between their maximum slots and their actually assigned slots is called the "unassigned capacity of staff member i". The maximum unassigned capacity across all staff members, namely

\max_{1 \leq i \leq N} (R_i - X_i)

is defined as the "unfairness".

A large unfairness means that there exists a staff member whose assignment is extremely small relative to their maximum. Takahashi wants to minimize the unfairness in order to reduce the dissatisfaction of such staff members as much as possible.

When an assignment satisfying the total condition exists, find the minimum value of the unfairness. If no assignment satisfying the total condition exists, output -1.

Note that an assignment satisfying the total condition does not exist if and only if M > R_1 + R_2 + \cdots + R_N.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 10^{18}
• 0 \leq R_i \leq 10^{18} (1 \leq i \leq N)
• All input values are integers.

Note: R_1 + R_2 + \cdots + R_N may exceed the range of a 64-bit signed integer.

Sample Input 1

3 7
4 3 5

Sample Output 1

2

Sample Input 2

3 20
5 5 5

Sample Output 2

-1

Sample Input 3

5 1000000000000000000
300000000000000000 200000000000000000 400000000000000000 100000000000000000 500000000000000000

Sample Output 3

100000000000000000

Problem Statement

Takahashi is an adventurer about to challenge a dungeon. He has a total of N pieces of equipment, where the i-th piece of equipment (i = 1, 2, \ldots, N) has a defense power of W_i and an attack power of S_i.

The dungeon he is about to challenge is extremely dangerous, and he cannot enter unless the total defense power of his equipped items is at least K. Takahashi can choose and equip anywhere from 0 to N pieces of equipment out of the N available. However, the same piece of equipment cannot be chosen more than once.

Among all ways to choose equipment such that the total defense power is at least K, Takahashi wants to maximize the total attack power.

If there exists a selection of equipment whose total defense power is at least K, output the maximum total attack power. If no such selection exists, output -1.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 10^4
• 1 \leq W_i \leq 10^4
• 1 \leq S_i \leq 10^5
• All input values are integers

Sample Input 1

4 5
3 8
1 3
3 7
2 2

Sample Output 1

20

Sample Input 2

3 50
6 100
8 200
5 150

Sample Output 2

-1

Sample Input 3

10 30
5 80
1 10
8 90
4 50
6 70
3 40
2 30
7 60
9 50
10 50

Sample Output 3

530

Problem Statement

Takahashi is walking along a stone-paved path in a garden. The path has N stepping stones arranged in a row, numbered 1, 2, \ldots, N from left to right. Each stepping stone i has a score A_i representing its scenic evaluation. Scores can be negative.

Takahashi starts at stepping stone 1 and moves to stepping stone N. When currently on stepping stone i, he can take one of the following actions:

• Step forward: Move to stepping stone i + 1 (only if i + 1 \leq N).
• Skip one stone: Jump over stepping stone i + 1 without visiting it, and move to stepping stone i + 2 (only if i + 2 \leq N).

Since the "skip one stone" action is physically exhausting, it can be performed at most K times throughout the entire journey from stepping stone 1 to stepping stone N (it is also fine to use it 0 times). There is no limit on the number of "step forward" actions.

Takahashi ends his journey upon reaching stepping stone N. Maximize the total score of all stepping stones that Takahashi visits during his journey (including the starting stone 1 and the destination stone N). Find this maximum value.

Note that by using only "step forward" actions without any "skip one stone" actions, Takahashi can always reach stepping stone N, so a valid way of moving always exists.

Constraints

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

Sample Input 1

5 1
3 -5 4 -2 6

Sample Output 1

11

Sample Input 2

4 0
-1 2 -3 4

Sample Output 2

2

Sample Input 3

12 3
5 -10 8 -3 7 -20 4 6 -2 9 -15 10

Sample Output 3

44

Sample Input 4

30 10
12 -5 7 -100 20 3 -8 15 -30 6 9 -2 -50 25 4 -1 18 -40 11 13 -7 5 -60 30 2 -3 16 -20 8 10

Sample Output 4

211

Sample Input 5

2 2
-1000000000 -1000000000

Sample Output 5

-2000000000