Problem Statement

Takahashi is the president of the handicrafts club. As preparation for the cultural festival, he needs to cut N ribbons into specified lengths to make decorative parts.

The i-th ribbon has a length of L_i millimeters, and the specified length per part is T_i millimeters. For each ribbon, parts of T_i millimeters are cut out sequentially from one end. The number of parts obtained this way is \lfloor L_i / T_i \rfloor, and the length of the leftover scrap after cutting is R_i = L_i \bmod T_i millimeters.

The advisor, Teacher Aoki, has established the following rule: "If there is a remaining scrap (R_i > 0) and its length is at least half of the specified length, that is, R_i \geq \lfloor T_i / 2 \rfloor, then that scrap may also be used as one part."

In summary, the number of parts P_i obtained from the i-th ribbon is determined as follows:

P_i = \begin{cases} \lfloor L_i / T_i \rfloor + 1 & \text{(if } R_i > 0 \text{ and } R_i \geq \lfloor T_i / 2 \rfloor \text{)} \\ \lfloor L_i / T_i \rfloor & \text{(otherwise)} \end{cases}

Here, "otherwise" refers to either the case where no scrap remains (R_i = 0), or the case where a scrap remains but its length is less than \lfloor T_i / 2 \rfloor (0 < R_i < \lfloor T_i / 2 \rfloor).

Note that this rule applies in the same way even when L_i < T_i. In this case, \lfloor L_i / T_i \rfloor = 0, and the entire ribbon becomes a scrap of length R_i = L_i. If the scrap length is at least \lfloor T_i / 2 \rfloor, then one part is obtained; otherwise, zero parts are obtained.

For each of the N ribbons, determine the number of parts obtained.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq 10^{18}
• 1 \leq T_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5
10 3
10 5
7 4
7 5
7 6

Sample Output 1

4
2
2
2
1

Sample Input 2

5
5 3
4 3
3 7
2 7
100 100

Sample Output 2

2
2
1
0
1

Sample Input 3

8
1000 300
1000 400
999 500
123456 789
50 99
50 100
50 101
1 1

Sample Output 3

3
3
2
156
1
1
1
1

Sample Input 4

10
1000000000000000000 1
1000000000000000000 3
999999999999999999 2
1000000000000000000 1000000000000000000
999999999999999999 1000000000000000000
500000000000000000 1000000000000000000
499999999999999999 1000000000000000000
7 2
123456789012345678 987654321
1000000000000000000 7

Sample Output 4

1000000000000000000
333333333333333334
500000000000000000
1
1
1
0
4
124999999
142857142857142857

Sample Input 5

6
1 1
1 2
1 3
1 1000000000000000000
1000000000000000000 1000000000000000000
2 1

Sample Output 5

1
1
1
0
1
2

Problem Statement

Takahashi is analyzing a certain sequence.

He is given a sequence of N integers A_1, A_2, \ldots, A_N. Takahashi wants to select a contiguous subarray from this sequence such that the sum of its elements is maximized.

Specifically, he chooses a pair of integers (l, r) satisfying 1 \leq l \leq r \leq N, and computes the subarray sum A_l + A_{l+1} + \cdots + A_r.

It is also permitted to select no elements (i.e., to choose an empty subarray), in which case the sum is defined to be 0.

Find the maximum sum among all possible choices.

Constraints

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

Sample Input 1

5
3 -1 4 -2 2

Sample Output 1

6

Sample Input 2

8
-2 1 -3 4 -1 2 1 -5

Sample Output 2

6

Sample Input 3

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

Sample Output 3

0

Problem Statement

Takahashi's room has N lights numbered from 1 to N. Initially, all lights are turned off.

Takahashi will perform M operations. In the j-th operation (1 \leq j \leq M), he toggles the switches of all lights whose numbers are between L_j and R_j, inclusive. That is, among those lights, the ones that are on are turned off, and the ones that are off are turned on.

Find the number of lights that are on after all M operations have been completed.

Constraints

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

Sample Input 1

5 2
1 3
2 4

Sample Output 1

2

Sample Input 2

6 3
1 4
2 5
3 6

Sample Output 2

4

Sample Input 3

20 5
1 10
5 15
3 8
1 20
10 15

Sample Output 3

13

Sample Input 4

1000 6
1 500
250 750
1 1000
400 600
1 100
800 900

Sample Output 4

499

Sample Input 5

1 1
1 1

Sample Output 5

1

Problem Statement

Takahashi walks from his home to school every day. Recently, a stray dog has been spotted near a certain point along his school route. The stray dog is based at a specific point and roams around its vicinity.

Takahashi wants to choose a route that stays as far away from the stray dog's base as possible.

The town consists of N points and M bidirectional roads. Each point is numbered from 1 to N. Each road i (1 \leq i \leq M) connects point U_i and point V_i, and takes W_i minutes to traverse (W_i is a positive integer).

Takahashi's home is at point S, his school is at point T, and the stray dog's base is at point P.

The shortest travel time d(X) from the stray dog's base at point P to a point X is defined as follows:

• d(P) = 0.
• When point X (X \neq P) is reachable from point P, d(X) is the minimum travel time (sum of W_i of the roads traversed) over all paths from point P to point X.
• If point X is not reachable from point P, then d(X) = +\infty.

Here, +\infty is considered larger than any finite value.

A simple path from point S to point T is a sequence of points v_0, v_1, \ldots, v_k (where k \geq 1, v_0 = S, v_k = T) satisfying all of the following conditions:

• v_0, v_1, \ldots, v_k are all distinct (no point is visited more than once).
• For all 1 \leq j \leq k, there exists a road connecting point v_{j-1} and point v_j.

The safety score of a simple path v_0, v_1, \ldots, v_k is defined as the minimum value of d over all points on the path, including the start and end points, namely:

\min(d(v_0), d(v_1), \ldots, d(v_k))

Here, if the values of d include both finite values and +\infty, the \min takes the minimum among the finite values. The safety score is +\infty only when all d(v_j) are +\infty.

The safety score represents how far the closest point to the stray dog's base along the route is from that base.

Among all simple paths from point S to point T that Takahashi can choose, find the maximum safety score.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq S, T, P \leq N
• S \neq T
• S and P, as well as T and P, may coincide
• 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
• U_i \neq V_i (1 \leq i \leq M)
• 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
• There is at most one road connecting any pair of points
• There exists at least one simple path from point S to point T
• All input values are integers

Sample Input 1

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

Sample Output 1

1

Sample Input 2

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

Sample Output 2

INF

Sample Input 3

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

Sample Output 3

4

Sample Input 4

12 16
1 12 6
1 2 3
2 3 4
3 6 2
6 12 1
1 4 5
4 5 3
5 9 2
9 10 4
10 11 3
11 12 2
4 8 6
8 12 7
2 7 1
7 11 5
5 6 8
8 9 1

Sample Output 4

1

Sample Input 5

2 1
1 2 1
1 2 1000000000

Sample Output 5

0

Problem Statement

There are N cities in a region, numbered from 1 to N. Between the cities, M communication cables have been laid, and each cable allows bidirectional communication. The i-th cable (1 \leq i \leq M) connects city U_i and city V_i, and its maintenance cost is a positive integer W_i. The graph contains no self-loops or multiple edges.

This graph is 2-edge-connected. That is, even if any single cable among the M cables is removed, communication between any two cities remains possible using the remaining cables.

Takahashi is the communication administrator of this region and is trying to build a "backbone network" by selecting exactly N - 1 cables that connect all cities. Such a selection of N - 1 cables corresponds to a spanning tree. Takahashi selects cables so that the total maintenance cost of the cables included in the backbone network is as small as possible. In other words, Takahashi constructs a minimum spanning tree.

On the other hand, Aoki is an engineer from a rival company. Before Takahashi constructs the backbone network, Aoki can choose exactly 1 cable from the M cables and cut it. A cut cable becomes unusable and cannot be included in the backbone network. Since the graph is 2-edge-connected, it is guaranteed that no matter which cable is cut, a spanning tree can still be constructed from the remaining M - 1 cables.

The flow of this game is as follows:

1. Aoki chooses exactly 1 cable from the M cables and cuts it.
2. Takahashi selects N - 1 cables from the remaining M - 1 cables and constructs a spanning tree with the minimum total maintenance cost (minimum spanning tree).

Aoki chooses which cable to cut so as to maximize the total maintenance cost, anticipating that Takahashi will construct a minimum spanning tree.

Note that even if multiple minimum spanning trees exist, their total maintenance cost is uniquely determined. Therefore, once Aoki decides which cable to cut, the total maintenance cost of the backbone network Takahashi constructs is also uniquely determined.

Find the total maintenance cost of the backbone network when Aoki sabotages optimally and Takahashi constructs the network optimally.

Constraints

• 3 \leq N \leq 10^5
• N \leq M \leq 2 \times 10^5
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i (no self-loops)
• If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j) (no multiple edges)
• 1 \leq W_i \leq 10^9
• W_i is an integer
• The graph is 2-edge-connected (the graph remains connected after removing any single edge)
• It is guaranteed that the answer is at most 2 \times 10^{14}

Sample Input 1

3 3
1 2 1
2 3 2
1 3 3

Sample Output 1

5

Sample Input 2

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

Sample Output 2

9

Sample Input 3

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

Sample Output 3

20

Sample Input 4

8 12
1 2 10
2 3 20
3 4 30
4 5 40
5 6 50
6 7 60
7 8 70
8 1 80
1 5 15
2 6 25
3 7 35
4 8 45

Sample Output 4

210

Sample Input 5

3 3
1 2 1000000000
2 3 1000000000
1 3 1000000000

Sample Output 5

2000000000