Problem Statement

Takahashi manages the power grid of a region consisting of N cities. Each city is numbered from 1 to N, and city i has a required power amount (demand) S_i needed to function properly.

There are M power transmission lines in this region, each connecting two cities bidirectionally. The j-th transmission line connects city U_j and city V_j and has a transmission capacity of W_j. Each transmission line can supply power equal to its transmission capacity to each of the two cities it connects.

The power amount T_i that can be supplied to city i is defined as the sum of the transmission capacities of all transmission lines that have city i as an endpoint. That is, if the transmission capacities of the transmission lines with city i as an endpoint are W_{j_1}, W_{j_2}, \ldots, W_{j_k}, then T_i = W_{j_1} + W_{j_2} + \cdots + W_{j_k}. If there are no transmission lines with city i as an endpoint, then T_i = 0.

City i is called a "power-deficient city" if T_i < S_i holds.

Find the number of power-deficient cities.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
• 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
• There is at most one transmission line connecting the same pair of cities (i.e., all pairs (U_j, V_j) are distinct)
• All input values are integers

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

0

Sample Input 3

6 5
10 20 15 8 30 5
1 2 7
2 3 10
3 4 5
4 5 3
1 6 6

Sample Output 3

2

Sample Input 4

10 8
100 50 200 30 80 60 150 40 90 10
1 2 25
2 3 30
3 4 50
4 5 20
5 6 35
6 7 40
7 8 60
9 10 5

Sample Output 4

6

Sample Input 5

1 0
1

Sample Output 5

1

Problem Statement

There are N pillars lined up in a row in front of Takahashi. The durability of the i-th pillar from the left is A_i.

Takahashi simultaneously applies the same force X to all pillars. Each pillar that receives the impact has its durability decreased by X.

After that, a chain reaction propagates from left to right. Specifically, when a pillar collapses (its durability becomes 0 or less), the durability of the pillar immediately to its right decreases by an additional 1. If this causes the right neighbor to also collapse, the durability of the pillar immediately to its right decreases by 1 as well. This chain continues to the right until a pillar does not collapse. Note that if the rightmost pillar collapses, no further chain reaction occurs.

In summary, whether each pillar collapses is determined from left to right by the following rule: in addition to the direct impact X, a pillar receives an additional 1 damage if the pillar immediately to its left has collapsed.

Find the minimum value of X required to collapse all pillars. X must be a positive integer.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

4
2 3 2 4

Sample Output 1

3

Sample Input 2

5
5 2 2 2 2

Sample Output 2

5

Sample Input 3

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

Sample Output 3

9

Sample Input 4

30
8 12 9 13 10 14 11 15 12 16 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 25 22 26

Sample Output 4

25

Sample Input 5

1
1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is the administrator of a network consisting of N computers and 1 central server. The N computers are numbered from 1 to N, and the central server is numbered as computer 0. That is, the entire network consists of a total of N + 1 computers: computers 0, 1, \ldots, N.

Each computer i (1 \leq i \leq N) is directly connected to a parent computer P_i (0 \leq P_i \leq N, P_i \neq i). These connections form a tree structure with N + 1 vertices rooted at the central server (computer 0). In this tree structure, a child computer of computer v refers to a computer j satisfying P_j = v.

One day, a virus infiltrated the network. Each computer i (1 \leq i \leq N) has a vulnerability value D_i assigned to it.

Virus infection targets only computers 1 through N. The central server (computer 0) is not subject to infection and will never become infected. Infection spreads in a chain reaction according to the following rules:

1. Initial infection: All computers with a positive vulnerability value (D_i > 0) become infected. Computers with a vulnerability value of 0 or less (D_i \leq 0) are not infected at this stage. However, they may become infected later through Rule 2 below.

1. Propagation of infection (child → parent direction): For a computer v (1 \leq v \leq N) that is not yet infected, let a be the number of infected child computers of v, and b be the number of non-infected child computers of v. If a > b is satisfied, then v becomes newly infected. This determination is made regardless of the vulnerability value D_v of computer v itself. That is, even if D_v \leq 0, v becomes infected if the condition on the infection status of its child computers is met. Note that for a computer with no child computers, a = b = 0, which does not satisfy a > b, so such a computer will not become infected by this rule. Infection only occurs in the direction where a parent becomes infected based on the infection status of its children. Even if a parent computer becomes infected, this does not cause its child computers to become newly infected.

1. Repetition: The determination and infection in Rule 2 are repeated until no new computers become infected in a round. The determination in each round is performed simultaneously for all computers based on the infection status at the beginning of that round. That is, if multiple computers become newly infected in a given round, they all become infected simultaneously, and the infection status does not change partway through the same round. The determination in the next round is based on the updated infection status.

Determine the total number of computers that are ultimately infected. The central server (computer 0) is not subject to infection and should not be included in the count.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq P_i \leq N, P_i \neq i (1 \leq i \leq N)
• The given connections form a tree structure with N + 1 vertices rooted at computer 0
• -10^9 \leq D_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

6
0 -1
1 1
1 2
1 0
2 -5
3 0

Sample Output 1

3

Sample Input 2

4
0 0
0 -3
0 -1
0 0

Sample Output 2

0

Sample Input 3

15
0 -5
1 -1
1 -1
1 0
2 1
2 1
2 0
3 -1
3 2
3 0
4 1
4 0
8 1
8 1
8 0

Sample Output 3

10

Sample Input 4

40
0 -100
1 0
1 -1
1 -1
2 -1
2 -1
2 3
3 -2
3 -2
3 -2
4 1
4 0
4 1
5 0
5 1
5 1
6 -1
6 2
7 0
7 -5
8 1
8 0
8 1
9 -1
9 -1
10 1
10 1
10 0
17 1
17 0
17 1
19 1
19 0
20 -1
20 -1
24 1
24 1
25 0
25 1
34 1

Sample Output 4

28

Sample Input 5

1
0 -1000000000

Sample Output 5

0

Problem Statement

Takahashi works at a renovation company and is responsible for covering room floors with square tiles.

Takahashi has received requests to tile the floors of N rectangular rooms. The floor of the i-th room has height H_i and width W_i.

Takahashi wants to choose exactly one type of square tile and use it to cover all room floors. In each room, tiles are placed parallel to the room's edges without gaps or overlaps. The side length of the square tile must be a positive integer.

The necessary and sufficient condition for a square tile with side length d to be able to tile the floor of room i is that both H_i and W_i are multiples of d. In this case, the number of tiles used in room i is C_i = \frac{H_i}{d} \times \frac{W_i}{d}.

Furthermore, due to design requirements, each room has a specified "design coefficient" S_i. The number of tiles C_i used in room i must be a multiple of S_i.

Takahashi wants to use tiles that are as large as possible. Find the maximum side length d of a square tile that simultaneously satisfies the above conditions for all rooms.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq H_i \leq 10^9
• 1 \leq W_i \leq 10^9
• 1 \leq S_i \leq 10^9
• For all i, H_i \times W_i is a multiple of S_i (this guarantees that d = 1 always satisfies the conditions, so an answer always exists)
• All inputs are integers

Sample Input 1

2
6 8 6
10 12 15

Sample Output 1

2

Sample Input 2

1
12 12 8

Sample Output 2

3

Sample Input 3

6
48 72 8
90 60 25
84 126 14
108 144 12
150 210 35
66 132 11

Sample Output 3

6

Sample Input 4

15
123456000 789000000 96
250000000 400000000 125000000
999999000 888888000 27
314159000 271828000 4
500001000 700002000 9
655360000 131072000 1024
100003000 300009000 3
777777000 222222000 6
12345000 67890000 15
987654000 321000000 18
400000000 600000000 100000000
864000000 972000000 7776
135790000 246800000 10000
999000000 1000000000 999
720720000 840840000 1001

Sample Output 4

200

Sample Input 5

1
1000000000 1000000000 1000000000

Sample Output 5

10000

Problem Statement

Takahashi is in charge of managing a flowerbed. The flowerbed has N flowers planted in a row, numbered 1, 2, \ldots, N from left to right.

Each flower i (1 \le i \le N) has a recorded "variety number" A_i and "height" B_i. Takahashi wants to select a contiguous interval of flowers to create an exhibition section. An interval [l, r] (1 \le l \le r \le N) chosen as the exhibition section is the contiguous sequence of flowers from flower l to flower r (including the case where l = r, i.e., only a single flower).

To make the exhibition section look attractive, Takahashi wants to choose an interval that satisfies both of the following 2 conditions simultaneously.

Condition 1 (Variety diversity condition):

Let D be the number of distinct values among the variety numbers A_l, A_{l+1}, \ldots, A_r of flowers in the interval [l, r]. The product of D and the length of the interval (r - l + 1) must be at most K. That is,

D \times (r - l + 1) \le K

must be satisfied.

Condition 2 (Height balance condition):

The difference between the maximum and minimum heights of flowers in the interval [l, r] must be at most M. That is,

\max_{l \le i \le r} B_i - \min_{l \le i \le r} B_i \le M

must be satisfied.

Find the number of intervals [l, r] (1 \le l \le r \le N) that satisfy both conditions above simultaneously.

Constraints

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

Sample Input 1

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

Sample Output 1

10

Sample Input 2

4 2 0
1 1 2 2
5 5 6 6

Sample Output 2

6

Sample Input 3

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

Sample Output 3

48

Sample Input 4

40 100 50
1 2 3 4 5 1 2 6 7 8 3 4 9 10 1 11 12 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12
100 120 130 160 170 150 140 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500

Sample Output 4

216

Sample Input 5

1 1 0
1
1000000000

Sample Output 5

1