Problem Statement

Takahashi and Aoki are walking on a number line.

At time 0, Takahashi is at coordinate X and Aoki is at coordinate Y. From now on, the two will move simultaneously every minute for T minutes.

Takahashi's movement is described by a string A of length T, and Aoki's movement is described by a string B of length T. The i-th character of A (1 \leq i \leq T) represents Takahashi's movement from time i-1 to time i, and the i-th character of B represents Aoki's movement during the same time period. The meaning of each character is as follows:

• L : The coordinate decreases by 1 (move in the negative direction)
• R : The coordinate increases by 1 (move in the positive direction)
• S : Stay in place (the coordinate does not change)

For each integer time i (1 \leq i \leq T), if the coordinates of the two people are equal at time i, we say they met at time i. Passing each other during movement does not count as a meeting, and time 0 is also not considered.

Find the number of times the two people meet during the T minutes, that is, the number of i (1 \leq i \leq T) such that the coordinates of the two people are equal at time i.

Constraints

• 1 \leq T \leq 10^6
• -10^9 \leq X \leq 10^9
• -10^9 \leq Y \leq 10^9
• T, X, Y are integers.
• A is a string of length T consisting of L, R, S.
• B is a string of length T consisting of L, R, S.

Sample Input 1

4 0 2
RRSS
SSLL

Sample Output 1

1

Sample Input 2

2 0 1
RS
LS

Sample Output 2

0

Sample Input 3

12 0 3
RRSRLSRSLSRS
SSSLSRSSLRSS

Sample Output 3

6

Sample Input 4

30 -10 15
RRSLSLRSSRRRSLSLRSSRRRSLSLRSSR
SLRSRSLLSRSLRSRSLLSRSLRSRSLLSR

Sample Output 4

0

Sample Input 5

1 0 0
R
L

Sample Output 5

0

Problem Statement

Takahashi is in charge of maintaining N machines at a factory. Takahashi cannot maintain multiple machines simultaneously and must maintain all N machines exactly once each.

Maintaining the i-th machine takes exactly T_i seconds of work time. Additionally, immediately after completing the maintenance of each machine, Takahashi must perform cleaning and servicing of the tools used (hereafter called "tool servicing"). Tool servicing for the i-th machine takes exactly R_i seconds. The time required for tool servicing is determined by each machine and does not depend on which machine is worked on next. All maintenance and tool servicing must be performed sequentially and cannot be done in parallel. The next machine's maintenance cannot begin until tool servicing is complete.

However, for the last machine to be maintained, since there is no machine to work on afterward, tool servicing can be skipped (and since skipping it results in an earlier completion time, it is always skipped).

Travel time between machines is negligible, and the next task can begin immediately after the previous one finishes.

That is, if the order of maintenance is (p_1, p_2, \ldots, p_N) (a permutation of (1, 2, \ldots, N)), the total time required to complete all maintenance is

\left(\sum_{k=1}^{N-1} (T_{p_k} + R_{p_k})\right) + T_{p_N}

Takahashi can maintain the N machines in any order he likes. If he starts working at time 0, find the earliest time at which all machine maintenance is completed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq T_i \leq 10^9
• 1 \leq R_i \leq 10^9
• All inputs are integers

Sample Input 1

3
5 3
3 7
8 2

Sample Output 1

21

Sample Input 2

5
10 4
7 9
3 1
6 9
2 5

Sample Output 2

47

Sample Input 3

8
100 80
200 500
150 60
300 200
50 90
400 100
250 300
180 150

Sample Output 3

2610

Problem Statement

Takahashi enjoys mountain climbing and is planning a traverse route through a mountain range. The mountain range has N points arranged in a line, numbered from 1 to N, and the elevation of each point i (1 \leq i \leq N) is A_i meters.

Takahashi chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and walks a route that passes through each point in order from point l to point r in ascending order of their numbers. The number of points included in this route is r - l + 1.

The total elevation change of this route is defined as the sum of the absolute differences in elevation between adjacent points along the route, namely:

\sum_{i=l}^{r-1} |A_{i+1} - A_i|

Note that when l = r, this sum is an empty sum, so the total elevation change is 0.

Takahashi wants to walk a route with a total elevation change of at least K for training purposes. However, since he is short on time, he wants to choose a route that satisfies the condition while containing the fewest number of points.

If a route with a total elevation change of at least K exists, find the minimum number of points included in such a route. If no such route exists, output -1.

Constraints

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

Sample Input 1

5 5
1 4 2 5 3

Sample Output 1

3

Sample Input 2

3 100
1 2 3

Sample Output 2

-1

Sample Input 3

10 15
0 10 3 8 1 9 2 7 4 6

Sample Output 3

3

Sample Input 4

20 500
0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100 0 100

Sample Output 4

6

Sample Input 5

1 1
1000000000

Sample Output 5

-1

Problem Statement

Takahashi works as a librarian at a library. Today, he must return N books that were returned by patrons to their correct positions on the shelves.

The library is on a number line, and the counter is located at coordinate 0. The shelf where the i-th book (1 \leq i \leq N) should be placed is at coordinate X_i. Shelves can exist in both the positive and negative directions from the counter. Different books may need to be returned to the same coordinate.

Takahashi starts at the counter (coordinate 0). He can carry at most K books at a time. He repeats the following procedure until all books have been returned:

1. At the counter (coordinate 0), choose between 1 and K books (inclusive) from among the books not yet returned, and take them out.
2. Move freely along the number line, and drop off each book when reaching the coordinate of its corresponding shelf. The order in which shelves are visited is free to choose. It is allowed to visit shelves in both the positive and negative directions within the same trip.
3. After all books taken out have been placed on their correct shelves, return to the counter (coordinate 0). This completes one round trip.

All books taken out must be placed on their correct shelves during that round trip. Books cannot be brought back to the counter to be carried on a later trip. After every round trip, including the last one, Takahashi must return to the counter.

The travel distance of one round trip is the total distance actually traveled along the number line during that trip. For example, if Takahashi moves from coordinate 0 to coordinate 5, then from there to coordinate -3, and then back to coordinate 0, the travel distance is 5 + 8 + 3 = 16.

The sum of travel distances across all round trips is called the total travel distance. Find the minimum total travel distance to return all books to their correct shelves and return to the counter.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• -10^9 \leq X_i \leq 10^9
• X_i \neq 0 (no shelf is at the counter's position)
• All input values are integers

Sample Input 1

3 2
1 3 5

Sample Output 1

12

Sample Input 2

5 2
-3 -1 2 4 6

Sample Output 2

22

Sample Input 3

8 3
-7 -5 -2 1 3 4 8 10

Sample Output 3

40

Problem Statement

Takahashi and Aoki manage N tasks numbered from 1 to N.

For the i-th task, a symbol S_i representing the person in charge and a work cost P_i are recorded. When S_i is T, the person in charge is Takahashi; when it is A, the person in charge is Aoki.

Here, flipping the assignment means changing T to A and A to T.

Q queries are given.

For the j-th query, you may perform the following operation at most once. It is also permitted to not perform the operation.

Operation: Choose a pair of integers (l, r) satisfying L_j \leq l \leq r \leq R_j, and flip the assignment of all tasks from the l-th to the r-th.

Consider the total work cost of tasks assigned to Aoki (A) among the tasks from the L_j-th to the R_j-th after the operation (or if no operation is performed). Find the minimum value of this total when the operation is chosen optimally.

Each query is independent. An operation in one query does not affect the original assignment/cost information or other queries.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• S_i is T or A
• 1 \leq P_i \leq 10^9
• 1 \leq L_j \leq R_j \leq N
• N, Q, P_i, L_j, R_j are integers

Sample Input 1

5 4
A 3
T 5
A 2
T 4
A 6
1 5
2 4
3 3
4 5

Sample Output 1

5
0
0
0

Sample Input 2

6 5
T 7
T 1
T 4
A 10
A 2
T 8
1 3
4 6
1 6
2 5
5 5

Sample Output 2

0
0
0
0
0

Sample Input 3

12 8
A 8
T 3
T 12
A 5
A 20
T 7
A 1
T 15
T 6
A 9
T 4
A 11
1 12
1 6
4 10
7 12
2 2
5 9
3 11
8 10

Sample Output 3

29
8
10
5
0
1
10
0

Sample Input 4

25 15
T 100
A 250
T 30
A 400
A 50
T 600
T 70
A 800
T 90
A 1000
A 110
T 1200
T 130
A 1400
T 150
A 1600
T 170
T 1800
A 190
A 2000
T 210
A 2200
T 230
A 2400
T 250
1 25
1 10
6 20
11 25
3 17
8 8
14 19
2 24
5 15
16 23
7 13
20 25
1 1
12 12
9 21

Sample Output 4

4680
790
3540
2670
2020
0
340
4680
1470
1810
90
440
0
0
3230

Sample Input 5

1 1
A 1000000000
1 1

Sample Output 5

0