Problem Statement

There are N students (numbered from 1 to N) in Takahashi's class.

In this class, there are M friendship relations. Friendships are bidirectional, and the i-th friendship means that student U_i and student V_i are friends with each other.

Here, the "popularity" of student k is defined as the sum of the numbers of student k's friends. For example, if student k's friends are students 2, 5, and 8 (three people), then the popularity of student k is 2 + 5 + 8 = 15. The popularity of a student who has no friends is 0.

Find the maximum value among the popularities of all N students.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i (no self-friendships)
• The same friendship is not given more than once (i.e., if i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j))
• All input values are integers

Sample Input 1

4 3
1 2
1 3
2 4

Sample Output 1

5

Sample Input 2

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

Sample Output 2

14

Sample Input 3

5 0

Sample Output 3

0

Problem Statement

Takahashi is in charge of inventory management for a retail chain that operates N stores. Each store holds products, and the i-th store (1 \leq i \leq N) currently has A_i products.

From now on, Q inventory updates will be performed in order. In the j-th update (1 \leq j \leq Q), the inventory of store X_j is overwritten to Y_j items. That is, regardless of the previous inventory count, the inventory of store X_j becomes exactly Y_j items.

For each update, determine the total inventory across all stores immediately after the update is completed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq X_j \leq N (1 \leq j \leq Q)
• 0 \leq Y_j \leq 10^9 (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

3 4
10 20 30
1 15
2 25
3 35
1 0

Sample Output 1

65
70
75
60

Sample Input 2

5 6
100 200 300 400 500
3 350
1 150
5 450
2 200
4 0
3 300

Sample Output 2

1550
1600
1550
1550
1150
1100

Sample Input 3

8 10
1000000000 500000000 250000000 125000000 62500000 31250000 15625000 7812500
1 0
2 1000000000
8 0
4 500000000
3 0
6 100000000
5 0
7 0
1 999999999
2 1

Sample Output 3

992187500
1492187500
1484375000
1859375000
1609375000
1678125000
1615625000
1600000000
2599999999
1600000000

Problem Statement

Takahashi is developing a meeting reservation management system for his company.

This company operates with a day lasting T minutes, and accepts meeting reservations during the time period from time 0 to time T. Each meeting has a designated start time and end time.

Takahashi wants to quantify the degree of reservation overlap. Specifically, he wants to find the maximum number of meetings taking place simultaneously at any given moment.

There are N meeting reservations, and the i-th reservation (1 \leq i \leq N) starts at time S_i and ends at time E_i. A meeting includes its start time but excludes its end time. That is, the time interval during which the i-th meeting takes place is the half-open interval [S_i, E_i).

At a given time t, the number of reservations satisfying S_i \leq t < E_i is called the "concurrent usage count" at that time.

Find the maximum concurrent usage count over all real numbers t satisfying 0 \leq t < T.

Note that different reservations may share the same start times or end times, and there may be multiple reservations with exactly the same time interval.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 0 \leq S_i < E_i \leq T (1 \leq i \leq N)
• All input values are integers

Sample Input 1

3 60
10 30
20 40
35 50

Sample Output 1

2

Sample Input 2

5 480
0 120
60 180
90 150
200 300
200 400

Sample Output 2

3

Sample Input 3

8 1000000000
100 500000000
100 999999999
200 300
200 400
200 500
999999000 1000000000
0 1000000000
50 150

Sample Output 3

6

Problem Statement

Takahashi is observing shooting stars at an observatory. He models the night sky as a grid with H rows and W columns, where the cell in the i-th row from the top and the j-th column from the left is denoted as (i, j) (1 \leq i \leq H, 1 \leq j \leq W). Row numbers increase from top to bottom, and column numbers increase from left to right.

N shooting stars appear in this night sky. The k-th shooting star (1 \leq k \leq N) appears at cell (R_k, C_k) at time 0, and moves one cell in the upper-left direction each time unit. That is, at time t (t = 0, 1, 2, \ldots), the k-th shooting star is located at cell (R_k - t, C_k - t). However, a shooting star that goes outside the grid (when R_k - t < 1 or C_k - t < 1) ceases to exist from that time onward.

In summary, the set of cells where the k-th shooting star exists is

\{(R_k - t,\ C_k - t) \mid t = 0, 1, \ldots, \min(R_k, C_k) - 1\}

Takahashi selects 0 or more cells on the grid and places one camera at each selected cell. The cells where cameras are placed can be freely chosen from any cells within the grid. Each camera remains fixed at its installed cell throughout all times.

If a shooting star is present at a cell where a camera is installed at any point in time, that shooting star is captured by that camera. A single camera can capture all shooting stars that pass through its installed cell (including those that pass through at different times).

Find the minimum number of cameras that need to be installed so that every shooting star is captured by at least one camera.

Constraints

• 1 \leq H \leq 10^9
• 1 \leq W \leq 10^9
• 1 \leq N \leq 2 \times 10^5
• 1 \leq R_k \leq H (1 \leq k \leq N)
• 1 \leq C_k \leq W (1 \leq k \leq N)
• All (R_k, C_k) are distinct (i.e., no two shooting stars share the same initial position)
• All input values are integers

Sample Input 1

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

Sample Output 1

3

Sample Input 2

3 4 4
1 4
2 2
3 1
3 4

Sample Output 2

4

Sample Input 3

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

Sample Output 3

7

Sample Input 4

1000000000 1000000000 40
1 1
1 1000000000
1000000000 1
1000000000 1000000000
999999999 999999999
999999998 999999997
999999997 999999998
500000000 500000000
500000001 500000000
500000000 500000001
123456789 987654321
987654321 123456789
314159265 271828182
271828182 314159265
42 999999999
999999999 42
2 2
3 3
4 4
5 5
10 20
20 10
100 200
200 100
1000 2000
2000 1000
12345 54321
54321 12345
111111111 222222222
222222222 111111111
333333333 444444444
444444444 333333333
555555555 666666666
666666666 555555555
777777777 888888888
888888888 777777777
135791357 246802468
246802468 135791357
999999000 999998000
999998000 999999000

Sample Output 4

23

Sample Input 5

1 1 1
1 1

Sample Output 5

1

Problem Statement

Takahashi and Aoki are playing a two-player game.

The board consists of N squares arranged in a row, numbered 1, 2, \ldots, N from left to right. Square i contains A_i stones.

There are also M arrows on the board. The j-th arrow is a one-way path from square U_j to square V_j (where U_j > V_j, meaning it always points from a square with a larger index to a square with a smaller index). This condition ensures that it is impossible to return to the same square by following the arrows.

Takahashi goes first, and the two players take turns making the following move:

Move: Choose a square that has at least 1 stone and at least 1 outgoing arrow. Take 1 stone from that square, choose 1 outgoing arrow from that square, and move the stone to the destination square of the arrow.

The player who cannot make a move (i.e., when it is their turn and there are no squares with both at least 1 stone and at least 1 outgoing arrow) loses. (If there are no stones on the board at all, the player also cannot make a move and loses.)

Before the game begins, Takahashi must perform a "removal" exactly once. A removal consists of choosing any square i and removing all stones from that square (setting A_i to 0). It is allowed to choose a square that already has 0 stones, in which case the board remains unchanged. This choice allows him to effectively not perform any removal.

Assuming Takahashi chooses the target square for removal optimally and both players play optimally thereafter, find the number of squares Takahashi can choose for the "removal" such that he wins.

Constraints

• 1 \leq N \leq 10^6
• 0 \leq M \leq 10^5
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq V_j < U_j \leq N (1 \leq j \leq M)
• There is at most one arrow between any pair of starting and ending squares. That is, if i \neq j, then (U_i, V_i) \neq (U_j, V_j).
• All input values are integers.

Sample Input 1

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

Sample Output 1

0

Sample Input 2

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

Sample Output 2

4

Sample Input 3

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

Sample Output 3

9

Sample Input 4

30 35
0 12 5 0 9 3 14 0 1 7 20 2 0 11 4 6 13 0 8 15 1 10 0 19 5 2 17 0 6 21
2 1
3 1
4 2
5 2
5 3
6 1
6 4
7 3
8 5
9 4
9 7
10 6
11 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 23
27 24
28 25
29 26
30 27
30 15
28 10
25 5

Sample Output 4

8

Sample Input 5

1 0
1000000000

Sample Output 5

0