Problem Statement

Takahashi is planning to set up a booth at a flea market. He has N items on hand, and the selling price of the i-th item is A_i yen.

However, each item requires preparation such as packaging and display before it can be sold. The preparation cost of the i-th item is B_i yen.

Takahashi can choose some items from the N items to sell. He may choose not to sell any items at all. He can independently decide whether or not to sell each item, but he cannot sell the same item more than once.

When he chooses a set of items S to sell, the profit is calculated as follows:

\text{Profit} = \sum_{i \in S} A_i - \sum_{i \in S} B_i

If no items are chosen, the profit is 0 yen.

Find the maximum profit that Takahashi can obtain.

Constraints

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

Sample Input 1

3
10 3
5 8
7 2

Sample Output 1

12

Sample Input 2

3
3 5
2 7
1 4

Sample Output 2

0

Sample Input 3

10
100 50
30 80
200 199
15 15
500 100
60 120
45 30
90 90
300 250
10 1000

Sample Output 3

516

Sample Input 4

20
1000000000 1
999999999 1000000000
500000000 400000000
300000000 300000001
750000000 250000000
100 200
999999999 999999998
123456789 987654321
800000000 100000000
450000000 450000000
600000000 500000000
50000000 90000000
1 1
700000000 650000000
350000000 400000000
200000000 100000000
888888888 111111111
10 10
500000000 500000001
999999999 2

Sample Output 4

4327777774

Sample Input 5

1
1 1000000000

Sample Output 5

0

Problem Statement

Takahashi is participating in a mission to investigate the surface of a planet by operating a space exploration robot. The robot needs to travel along a straight route from the base to the goal point.

The total length of the route is L meters, and N energy stations are installed along the route. The i-th energy station is located P_i meters from the base, where the battery can be charged by W_i units.

The robot's battery capacity is C units, and the battery is fully charged at departure. The robot consumes 1 unit of energy for every 1 meter it travels. When the robot arrives at an energy station, it can charge the available energy into its battery, but any amount exceeding the battery capacity will not be charged.

Before the mission begins, Takahashi checked the position and charge amount of each energy station. However, if the battery runs out along the way, the robot will stop and the mission will fail.

Find the maximum amount of energy remaining in the battery when the robot reaches the goal point. If the robot cannot reach the goal, output -1.

Constraints

• 1 \leq L \leq 10^9
• 0 \leq N \leq 2 \times 10^5
• 1 \leq C \leq 10^9
• 1 \leq P_i \leq L - 1 (1 \leq i \leq N)
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• P_1 < P_2 < \cdots < P_N (Energy stations are given in ascending order of distance from the base)
• All input values are integers

Sample Input 1

10 2 8
3 5
7 4

Sample Output 1

5

Sample Input 2

20 3 10
5 3
9 2
14 4

Sample Output 2

-1

Sample Input 3

100 5 50
10 30
25 20
40 35
60 25
80 15

Sample Output 3

25

Problem Statement

Takahashi has designed a graph consisting of N nodes and M directed edges. The nodes are numbered from 1 to N.

Each node i is assigned an interval [L_i, R_i] on the number line. Additionally, each node i has a recorded arrival position P_i and departure position Q_i.

Each directed edge has a starting node U_j, an ending node V_j, and a branch label B_j (0 or 1). Even if the same tuple (U_j, V_j, B_j) appears multiple times, each occurrence is treated as a separate edge.

This graph is called a valid binary decision tree if it satisfies all of the following conditions:

1. Rooted tree structure: The graph forms a rooted tree with node 1 as the root. That is, all of the following hold:

   • There are no edges entering node 1 (no edges with node 1 as their endpoint).
   • Each of nodes 2, 3, \dots, N has exactly one entering edge.
   • All nodes are reachable from node 1 by repeatedly following directed edges.

2. Out-degree constraint: For each node, there is at most one outgoing edge (an edge starting from that node) with label 0, and at most one outgoing edge with label 1.

3. Interval containment: For each edge u \to v, L_u < L_v and R_v < R_u hold. That is, the child's interval is strictly contained within the parent's interval.

4. Position consistency: For each edge u \to v, P_v = Q_u holds. That is, the departure position of the edge's starting node matches the arrival position of the edge's ending node.

5. Left-right ordering: When both a label 0 edge and a label 1 edge exist from a node u, letting their respective endpoints be x and y, the condition R_x < L_y holds.

Determine whether the given graph is a valid binary decision tree.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• N + M \leq 2 \times 10^5
• -10^9 \leq L_i < R_i \leq 10^9
• -10^9 \leq P_i \leq 10^9
• -10^9 \leq Q_i \leq 10^9
• 1 \leq U_j, V_j \leq N
• U_j \neq V_j
• B_j \in \{0, 1\}
• The same tuple (U_j, V_j, B_j) may be given multiple times.
• All inputs are integers.

Sample Input 1

3 2
0 10 0 100
1 3 100 200
5 8 100 300
1 2 0
1 3 1

Sample Output 1

YES

Sample Input 2

2 2
0 10 0 5
2 8 5 7
1 2 0
1 2 0

Sample Output 2

NO

Sample Input 3

10 9
-100 100 0 10
-90 -10 10 20
10 90 10 30
-80 -50 20 40
-40 -20 20 50
20 80 30 60
-75 -60 40 70
-38 -35 50 80
-30 -25 50 90
30 70 60 100
1 2 0
1 3 1
2 4 0
2 5 1
3 6 1
4 7 1
5 8 0
5 9 1
6 10 0

Sample Output 3

YES

Sample Input 4

20 19
-1000 1000 0 1
-900 -100 1 2
0 900 1 3
-850 -500 2 4
-400 -150 2 5
20 600 3 6
550 850 3 7
-840 -700 4 8
-650 -550 4 9
-350 -200 5 10
30 200 6 11
250 500 6 12
600 800 7 13
-830 -800 8 14
-640 -600 9 15
-340 -300 10 16
-280 -220 10 17
300 450 12 18
620 680 13 19
700 780 13 20
1 2 0
1 3 1
2 4 0
2 5 1
3 6 0
3 7 1
4 8 0
4 9 1
5 10 0
6 11 0
6 12 1
7 13 1
8 14 0
9 15 1
10 16 0
10 17 1
12 18 0
13 19 0
13 20 1

Sample Output 4

NO

Sample Input 5

1 0
-1000000000 1000000000 -1000000000 1000000000

Sample Output 5

YES

Problem Statement

Takahashi is the manager of an event venue.

He has received reservation requests for N events. The i-th event (1 \leq i \leq N) uses the venue during the time period from time L_i to time R_i.

Two events i, j have overlapping time periods if there exists a time t such that L_i \leq t < R_i and L_j \leq t < R_j. In other words, when each event's time period is represented as a half-open interval [L_i, R_i), the two intervals have a non-empty intersection. Therefore, if one event's end time coincides with another's start time (i.e., the intervals only touch at an endpoint), they are not considered overlapping.

Since there is only one venue, events with overlapping time periods cannot be accepted simultaneously. Takahashi will accept some of the N events and reject the rest. Any two events in the set of accepted events must have non-overlapping time periods. It is also allowed to accept no events (reject all) or, if there are no overlaps, to accept all events.

For each accepted event, a revenue of B ten-thousand yen is earned, regardless of the event's content. On the other hand, rejecting the i-th event incurs a cancellation compensation cost of C_i ten-thousand yen.

Takahashi wants to maximize the profit, which is the total revenue from accepted events minus the total cancellation compensation costs for rejected events.

Formally, let S \subseteq \{1, 2, \ldots, N\} be the set of accepted events, subject to the condition that any two events in S have non-overlapping time periods. Maximize the following value:

\displaystyle |S| \times B - \sum_{i \in \{1,\ldots,N\} \setminus S} C_i

Find this maximum value. Note that the answer may be negative.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq B \leq 10^9
• 0 \leq L_i < R_i \leq 10^9
• 1 \leq C_i \leq 10^9
• All input values are integers.

Sample Input 1

3 10
0 3 5
2 5 3
5 8 4

Sample Output 1

17

Sample Input 2

2 1
0 5 100
1 6 100

Sample Output 2

-99

Sample Input 3

8 15
0 10 5
5 20 8
10 25 3
20 30 12
25 35 7
30 40 6
35 50 9
0 50 100

Sample Output 3

-35

Sample Input 4

15 100
0 10 50
5 15 30
10 20 40
15 25 60
20 30 20
25 35 70
30 40 10
35 45 55
40 50 25
45 55 80
50 60 15
55 65 35
60 70 45
65 75 90
70 80 65

Sample Output 4

450

Sample Input 5

1 1000000000
0 1000000000 1000000000

Sample Output 5

1000000000

Problem Statement

N stones are arranged in a circle. The stones are numbered from 1 to N in clockwise order, and stone i has the lowercase English letter S_i engraved on it. The next stone clockwise from stone N is stone 1.

For a starting position x (1 \leq x \leq N) and a length \ell (1 \leq \ell \leq N), define the string C(x, \ell) as follows:

• C(x, \ell): The string of length \ell obtained by reading \ell stones consecutively in clockwise order starting from stone x.

That is, the k-th character (1 \leq k \leq \ell) of C(x, \ell) is the character engraved on stone ((x + k - 2) \bmod N) + 1.

Takahashi's current position is represented by a variable P. The initial value of P is 1.

Q queries are given in order. In the i-th query, integers A_i and L_i are given, and the following operations are performed:

1. Move: Update the current position P to the stone A_i positions ahead in the clockwise direction. That is,

   P \leftarrow ((P + A_i - 1) \bmod N) + 1

   (When A_i = 0, P does not change.)

2. Count: Compute and output the following value:

   \#\{\, (x, \ell) \mid 1 \leq x \leq N,\ 1 \leq \ell \leq L_i,\ C(x, \ell) < C(P, \ell) \,\}

Here, C(x, \ell) < C(P, \ell) denotes lexicographic comparison between strings of length \ell, where the lexicographic order follows the usual ordering of lowercase English letters \mathrm{a} < \mathrm{b} < \cdots < \mathrm{z}.

In other words, among all pairs (x, \ell) with starting position x (1 \leq x \leq N) and length \ell (1 \leq \ell \leq L_i), count the number of pairs for which C(x, \ell) is strictly lexicographically smaller than C(P, \ell).

Constraints

• 1 \leq N \leq 3000
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of lowercase English letters
• 0 \leq A_i \leq N - 1 (1 \leq i \leq Q)
• 1 \leq L_i \leq N (1 \leq i \leq Q)
• All inputs are integers (except for S)

Sample Input 1

5 4
abaca
0 1
1 3
3 5
4 2

Sample Output 1

0
9
0
8

Sample Input 2

4 5
aaaa
0 1
1 2
2 3
3 4
0 4

Sample Output 2

0
0
0
0
0

Sample Input 3

12 8
bananaabcxyz
0 6
5 4
11 12
3 7
8 2
1 10
10 11
6 5

Sample Output 3

24
0
84
34
2
70
86
30

Sample Input 4

30 15
qwertyuiopasdfghjklzxcvbnmabcd
0 1
29 30
15 10
7 25
3 3
28 30
14 1
1 29
20 15
5 30
0 12
11 20
27 7
6 18
2 30

Sample Output 4

20
209
100
124
51
750
24
348
30
240
96
180
6
234
450

Sample Input 5

1 5
z
0 1
0 1
0 1
0 1
0 1

Sample Output 5

0
0
0
0
0