Problem Statement

Takahashi's class is holding a present exchange at their Christmas party. There are N students in the class, each assigned a student number from 1 to N.

The rules for the present exchange are as follows. Each student prepares exactly 1 present and chooses one classmate other than themselves to give it to. Multiple students may choose the same recipient.

After the present exchange, Takahashi noticed that some students didn't receive any presents at all.

Given the student number T_i of the recipient that each student i (1 \leq i \leq N) gives their present to, find the number of students who didn't receive any presents.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq T_i \leq N
• T_i \neq i (no student gives a present to themselves)
• All input values are integers

Sample Input 1

5
2 1 1 2 3

Sample Output 1

2

Sample Input 2

8
2 3 4 5 6 7 8 1

Sample Output 2

0

Sample Input 3

10
3 1 1 1 3 7 8 7 10 9

Sample Output 3

4

Problem Statement

Takahashi is planning a trip lasting N days.

Before the start of day 1 of the trip, Takahashi has X yen in hand.

On each day i (1 \leq i \leq N), the following operations are performed in order:

1. He receives an income of A_i yen (such as daily wages from a part-time job or an allowance from family).
2. He has an expenditure of B_i yen (such as accommodation or food costs).

If his amount of money just before the start of day i's operations is S, then his amount of money just after all of day i's operations are completed is S + A_i - B_i yen.

When processing days 1 through N in order, find the minimum value of a non-negative integer X such that for all i (1 \leq i \leq N), the amount of money just after all of day i's operations are completed is at least 0.

Note that there is no condition on the amount of money during the middle of each day's operations. The condition only checks the amount of money just after all of each day's operations are completed.

Constraints

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

Sample Input 1

3
1 3
4 3
2 4

Sample Output 1

3

Sample Input 2

4
5 2
0 1
3 3
2 1

Sample Output 2

0

Sample Input 3

8
3 7
10 2
1 6
0 3
8 1
2 5
4 4
1 2

Sample Output 3

4

Sample Input 4

15
100 300
50 20
0 100
500 10
30 80
1000 1200
200 50
0 500
700 100
60 70
90 400
1000000000 999999900
1 100
500 0
100 600

Sample Output 4

380

Sample Input 5

1
0 1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi rolls a ball on a billiard table of length M. The billiard table is represented as a one-dimensional interval [0, M].

The initial position of the ball is at coordinate S. Takahashi performs N shots in order. The i-th shot is represented by a direction C_i and a distance A_i.

• If C_i = L, the ball is rolled to the left (in the direction of decreasing coordinate) by a distance of A_i.
• If C_i = R, the ball is rolled to the right (in the direction of increasing coordinate) by a distance of A_i.

The ball never leaves the interval [0, M]. If, while rolling, the ball reaches an endpoint 0 or M and there is still remaining travel distance, the direction of travel is immediately reversed and the ball continues rolling. This reversal is called one reflection. Multiple reflections may occur within a single shot.

Additionally, if at the start of a shot the ball is at endpoint 0 and C_i = L, or at endpoint M and C_i = R, the direction of travel is immediately reversed without consuming any travel distance, and this also counts as one reflection.

However, for a shot with A_i = 0, regardless of the ball's position or direction, no movement or reflection occurs at all.

Find the final position of the ball and the total number of reflections that occurred after processing all N shots.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^9
• 0 \leq S \leq M
• C_i is L or R
• 0 \leq A_i \leq 10^9
• N, M, S, A_i are all integers

Sample Input 1

3 10 4
R 3
L 5
R 8

Sample Output 1

10 0

Sample Input 2

4 5 0
L 2
R 3
R 1
L 0

Sample Output 2

4 2

Sample Input 3

10 17 8
R 12
L 4
L 20
R 0
R 35
L 1
R 17
L 18
R 5
L 33

Sample Output 3

17 7

Sample Input 4

20 1000000000 123456789
R 987654321
L 1000000000
R 1
R 999999999
L 500000000
L 750000000
R 250000000
L 0
R 1000000000
L 999999998
R 333333333
L 666666666
R 123456789
L 987654321
R 400000000
R 600000000
L 100000000
R 900000000
L 800000000
R 700000000

Sample Output 4

713580243 10

Sample Input 5

1 1 0
L 0

Sample Output 5

0 0

Problem Statement

Takahashi manages N servers. Each server is numbered from 1 to N, and the communication load of server i is A_i.

Takahashi is trying to connect these servers with network cables to build a connected network where all servers can communicate with each other, either directly or through other servers. When N = 1, the network is considered connected without using any cables.

Takahashi has M network cables, and the bandwidth of cable j is L_j. For each cable, Takahashi can choose two distinct servers and connect them with that cable. However, to connect server u and server v (u \neq v) with cable j, the bandwidth of the cable must be at least the sum of the communication loads of both servers, i.e., L_j \geq A_u + A_v must be satisfied.

The following constraints apply to the use of cables:

• Each cable can be used to connect at most one pair of servers. It is acceptable to leave some cables unused.
• Multiple cables cannot be connected between the same two servers. However, the network as a whole is allowed to contain cycles.

Determine whether it is possible to connect all servers into a single connected network. If it is possible, output Yes; otherwise, output No.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 2
1 2 3
4 5

Sample Output 1

Yes

Sample Input 2

4 5
3 1 4 2
5 6 4 7 3

Sample Output 2

Yes

Sample Input 3

5 3
10 20 30 40 50
25 35 45

Sample Output 3

No

Problem Statement

Takahashi manages a large-scale network consisting of N servers. The servers are numbered from 1 to N.

The network has M one-way communication links. The i-th link (1 \leq i \leq M) can transmit data from server U_i to server V_i. There may be multiple links with the same source-destination pair, but there are no links where the source and destination are the same server (no self-loops). Each server j (1 \leq j \leq N) has a current security level defined as an integer value W_j.

Here, server x is said to be "reachable" to server y if it is possible to reach server y from server x by following one or more links in their directed order. The case x = y is no exception: server x being reachable to itself means that starting from x, one can follow one or more links and return to x, i.e., there exists a directed cycle containing x.

To improve the security of the entire network, Takahashi can perform the following operation any number of times (including 0 times). In each operation, any server from 1 to N may be chosen, and the same server may be chosen multiple times.

Operation: Choose one server v. Let S(v) be the set of all servers u such that u is reachable from v and v is reachable from u (v itself is included in S(v) only if v is reachable from v). If S(v) is non-empty, increase the security level of all servers in S(v) by 1. If S(v) is empty, nothing happens.

In other words, when a directed cycle containing v exists, S(v) coincides with the set of all servers mutually reachable with v (the strongly connected component containing v), and the security levels of all these servers are increased by 1. When no directed cycle containing v exists, S(v) is the empty set, and performing the operation causes no change.

For each server j (1 \leq j \leq N), a "required level" is defined as an integer value T_j. The entire network is said to have met the standard when the security level of every server j is at least T_j.

Takahashi's goal is to bring the entire network to a state where the standard is met by repeating operations. Find the minimum total number of operations required.

If it is impossible to meet the standard regardless of how operations are performed, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq W_j \leq 10^9 (1 \leq j \leq N)
• 0 \leq T_j \leq 10^9 (1 \leq j \leq N)
• 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
• U_i \neq V_i (1 \leq i \leq M)
• All input values are integers

Sample Input 1

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

Sample Output 1

3

Sample Input 2

3 2
0 0 1
2 1 5
1 2
2 1

Sample Output 2

-1

Sample Input 3

10 14
10 5 7 1 2 100 0 4 10 3
12 9 7 3 6 50 5 8 12 3
1 2
2 3
3 1
3 4
4 5
5 4
5 6
6 7
7 8
8 9
9 7
2 4
4 5
8 10

Sample Output 3

13

Sample Input 4

20 31
100 95 98 90 0 10 5 50 1 2 3 4 5 1000 999 7 0 0 0 123
101 100 99 97 3 12 8 50 10 5 8 4 20 1000 1005 6 1 2 3 123
1 2
2 3
3 4
4 1
1 3
2 4
5 6
6 7
7 5
5 7
9 10
10 11
11 12
12 13
13 9
9 11
10 12
14 15
15 14
17 18
18 19
19 17
17 19
4 5
3 8
7 9
8 9
13 14
15 16
12 17
19 20

Sample Output 4

34

Sample Input 5

1 0
0
0

Sample Output 5

0