Problem Statement

Takahashi works in the logistics department of a company. The company has N warehouses, numbered from warehouse 1 to warehouse N. Each warehouse i (1 \leq i \leq N) currently stores P_i items.

Today, M shipping instructions to move items between warehouses have been issued. The j-th (1 \leq j \leq M) shipping instruction is "move W_j items from warehouse U_j to warehouse V_j." Here, U_j \neq V_j. There may be multiple shipping instructions between the same pair of warehouses.

The M shipping instructions are applied all at once, not sequentially. That is, the final number of items in each warehouse is obtained by taking the initial number of items, adding the total number of items coming into that warehouse, and subtracting the total number of items going out of that warehouse.

Takahashi wants to find the warehouse number with the most items after all shipping instructions have been applied. If there are multiple warehouses with the most items, find the one with the smallest warehouse number.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq P_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq U_j \leq N (1 \leq j \leq M)
• 1 \leq V_j \leq N (1 \leq j \leq M)
• U_j \neq V_j (1 \leq j \leq M)
• 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.
• It is guaranteed that after all shipping instructions have been applied, the number of items in each warehouse is 0 or more.

Sample Input 1

3 2
10 20 30
1 2 5
3 2 10

Sample Output 1

2

Sample Input 2

3 2
10 20 10
2 1 5
2 3 5

Sample Output 2

1

Sample Input 3

6 5
100 200 150 300 250 50
4 2 50
1 3 30
5 6 100
2 1 80
3 5 40

Sample Output 3

4

Sample Input 4

10 8
500 300 800 200 600 100 450 350 700 250
3 1 200
5 7 150
9 2 300
4 6 100
1 10 400
8 3 50
7 9 100
6 5 50

Sample Output 4

3

Sample Input 5

1 0
1000000000

Sample Output 5

1

Problem Statement

Takahashi works at a delivery company. Today, he needs to deliver N packages to their designated destinations. The destination of the i-th package is at coordinate D_i on a number line.

This delivery company has M distribution centers, and the j-th distribution center is located at coordinate S_j on the number line. Each package departs from exactly one distribution center and is transported to its destination. The cost of transporting package i from distribution center j to its destination is the distance |D_i - S_j|.

Each package must be assigned to exactly one distribution center. However, a single distribution center may handle multiple packages, and there may be distribution centers that handle no packages at all.

Minimize the total delivery cost of all packages.

That is, when assigning a distribution center f(i) (1 \leq f(i) \leq M) to each package i (1 \leq i \leq N), find the minimum value of

\sum_{i=1}^{N} |D_i - S_{f(i)}|

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• -10^9 \leq D_i \leq 10^9 (1 \leq i \leq N)
• -10^9 \leq S_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

3 2
1 4 7
3 6

Sample Output 1

4

Sample Input 2

5 3
-10 -3 0 5 15
-7 2 12

Sample Output 2

15

Sample Input 3

10 4
-100 -50 -20 0 10 30 60 80 200 500
-40 15 70 450

Sample Output 3

325

Problem Statement

Takahashi manages the power grid of a certain region. This power grid has N substations, numbered from 1 to N.

There are M transmission lines laid between substations. Transmission line k (1 \leq k \leq M) supplies power in the direction from substation U_k to substation V_k. There are no self-loops (U_k \neq V_k). Also, the same ordered pair (U_k, V_k) does not appear more than once. However, for two substations u, v, it is possible for a transmission line from substation u to substation v and a transmission line from substation v to substation u to exist simultaneously.

Each substation i (1 \leq i \leq N) has a durability value T_i. Also, each substation i has a non-negative integer value called its load. Initially, all substations are operational, and the load of substation i equals the number of transmission lines through which power flows into substation i, that is, the number of transmission lines k satisfying V_k = i (the in-degree of substation i in the directed graph).

In this power grid, when a substation's load exceeds its durability value, a blackout occurs, and it may spread in a chain reaction. The specific procedure is as follows.

Note that the load of a substation that has already experienced a blackout does not change afterwards.

1. Blackout occurrence: Among the substations that have not yet experienced a blackout, if there exists one whose load strictly exceeds its durability value (that is, for substation j, load > T_j), choose any one of them. Let the chosen substation be substation s. If no such substation exists, the chain ends.
2. Blackout processing: Substation s experiences a blackout and ceases to function. Since power transmission from substation s is cut off, each destination substation tries to compensate for the lost power through other routes, resulting in increased load. Specifically, for each transmission line k such that U_k = s, if the destination substation V_k has not yet experienced a blackout, the load of substation V_k is increased by 1 (the load of substations that have already experienced a blackout does not change).
3. Repeat: Return to step 1.

Since the number of substations is finite, this chain always terminates in a finite number of steps.

Note: It can be proven that regardless of which substation is chosen when multiple substations satisfy the condition in step 1, the final set of substations that experience a blackout is the same. Therefore, the answer is uniquely determined.

When the chain has completely settled (that is, when no substation that has not yet experienced a blackout has a load strictly exceeding its durability value), find all the substation numbers that ultimately experienced a blackout.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq T_i \leq N (1 \leq i \leq N)
• 1 \leq U_k \leq N (1 \leq k \leq M)
• 1 \leq V_k \leq N (1 \leq k \leq M)
• U_k \neq V_k (1 \leq k \leq M)
• The same ordered pair (U_k, V_k) does not appear more than once
• All input values are integers

Sample Input 1

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

Sample Output 1

3 4 5

Sample Input 2

3 2
0 1 1
1 2
1 3

Sample Output 2

-1

Sample Input 3

7 9
0 1 1 1 1 2 2
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 6

Sample Output 3

4 5 6 7

Sample Input 4

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

Sample Output 4

3 4 5 6 7 8 9 10

Sample Input 5

1 0
0

Sample Output 5

-1

Problem Statement

Takahashi is serving as the executive committee chairman of a school festival and has hired N part-time staff members. Each staff member i (1 \leq i \leq N) has a work efficiency V_i, which represents the amount of work they can complete per hour.

On the day of the school festival, M jobs have arisen. Each job j (1 \leq j \leq M) has a required workload D_j and a time limit of T_j hours for completion.

Takahashi decides whether to assign a staff member to each job. It is acceptable for some staff members to not be assigned to any job, and it is also acceptable for some jobs to remain incomplete without any staff assigned. However, the same staff member cannot be assigned to multiple jobs. In other words, each staff member can handle at most 1 job.

When staff member i is assigned to job j, the time required for the job is D_j / V_i hours. The job can be completed only if the required time does not exceed the time limit, that is, only if D_j / V_i \leq T_j (equivalently, V_i \times T_j \geq D_j) is satisfied. A staff member who does not satisfy this condition cannot be assigned to that job.

Determine the maximum number of jobs that can be completed when Takahashi optimally assigns the staff.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
• 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
• All inputs are integers

Sample Input 1

3 3
5 3 7
10 2
15 3
6 1

Sample Output 1

2

Sample Input 2

4 5
2 4 6 8
12 2
20 5
8 1
24 4
30 3

Sample Output 2

3

Sample Input 3

6 7
10 20 15 5 25 30
100 5
50 2
200 10
75 3
150 6
300 15
80 4

Sample Output 3

3

Problem Statement

Takahashi is hiking in a mountainous region. In this region, N mountains are lined up in a row, and the elevation of the i-th mountain from the left is H_i.

Takahashi stands at the summit of each mountain and looks to the left (in the direction of decreasing index). He enjoys counting how many mountains satisfying certain conditions are visible.

When looking to the left from the summit of mountain i, mountain j (j < i) is visible if and only if both of the following conditions are satisfied:

1. H_j > H_i. That is, mountain j is strictly higher than mountain i. In particular, if H_j = H_i, mountain j is not considered visible.
2. For all integers k satisfying j < k < i, H_k < H_j holds. That is, all mountains between mountain j and mountain i have elevations strictly lower than H_j.

Condition 2 means that if there is a mountain between mountain j and mountain i with elevation greater than or equal to H_j, then mountain j is blocked and not visible. When j = i - 1 (i.e., mountain j and mountain i are adjacent), there are no mountains between them, so condition 2 is automatically satisfied.

Note that the definition of "visible" in this problem is as described above and differs from a physical model of real line-of-sight occlusion.

Let C_i be the number of mountains visible to the left from the summit of mountain i. Since there are no mountains to the left of mountain 1, C_1 = 0.

Find the total of C_i for all i = 1, 2, \ldots, N, that is, \displaystyle\sum_{i=1}^{N} C_i.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq H_i \leq 10^9
• All inputs are integers.
• There may be multiple mountains with the same elevation.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

2

Sample Input 2

5
2 3 1 2 1

Sample Output 2

4

Sample Input 3

10
5 3 8 6 7 2 9 1 4 3

Sample Output 3

9

Sample Input 4

20
10 4 15 7 12 3 18 6 14 2 20 8 16 5 11 1 19 9 13 17

Sample Output 4

25

Sample Input 5

1
1000000000

Sample Output 5

0