Problem Statement

We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.

Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq 1000
• All values in input are integers.

Sample Input 1

3
1 1
2 1
3 1

Sample Output 1

3.000000000000000

The two flames will meet at 3 centimeters from the left end of the object.

Sample Input 2

3
1 3
2 2
3 1

Sample Output 2

3.833333333333333

Sample Input 3

5
3 9
1 2
4 6
1 5
5 3

Sample Output 3

8.916666666666668

Problem Statement

We have a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
(i,j) has a character G_{i,j} written on it. G_{i,j} is U, D, L, or R.

You are initially at (1,1). You repeat the following operation until you cannot make a move.

Let (i,j) be the square you are currently at.
If G_{i,j} is U and i \neq 1, move to (i-1,j).
If G_{i,j} is D and i \neq H, move to (i+1,j).
If G_{i,j} is L and j \neq 1, move to (i,j-1).
If G_{i,j} is R and j \neq W, move to (i,j+1).
Otherwise, you cannot make a move.

Print the square you end up at when you cannot make a move.
If you indefinitely repeat moving, print -1 instead.

Constraints

• 1 \leq H, W \leq 500
• G_{i,j} is U, D, L, or R.
• H and W are integers.

Sample Input 1

2 3
RDU
LRU

Sample Output 1

1 3

You will move as (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3), ending up here, so the answer is (1, 3).

Sample Input 2

2 3
RRD
ULL

Sample Output 2

-1

You will indefinitely repeat moving as (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots, so -1 should be printed in this case.

Sample Input 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

Sample Output 3

9 5

Problem Statement

A souvenir shop at AtCoder Land sells N boxes.

The boxes are numbered 1 to N, and box i has a price of A_i yen and contains A_i pieces of candy.

Takahashi wants to buy M out of the N boxes and give one box each to M people named 1, 2, \ldots, M.

Here, he wants to buy boxes that can satisfy the following condition:

• For each i = 1, 2, \ldots, M, person i is given a box containing at least B_i pieces of candy.

Note that it is not allowed to give more than one box to a single person or to give the same box to multiple people.

Determine whether it is possible to buy M boxes that can satisfy the condition, and if it is possible, find the minimum total amount of money Takahashi needs to pay.

Constraints

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

Sample Input 1

4 2
3 4 5 4
1 4

Sample Output 1

7

Takahashi can buy boxes 1 and 4, and give box 1 to person 1 and box 4 to person 2 to satisfy the condition.

In this case, he needs to pay 7 yen in total, and it is impossible to satisfy the condition by paying less than 7 yen, so print 7.

Sample Input 2

3 3
1 1 1
1000000000 1000000000 1000000000

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

19

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N and edges are numbered 1 to M. Edge i (1 \leq i \leq M) connects vertices u_i and v_i bidirectionally and has weight w_i.

For a path, define its weight as the maximum weight of an edge in the path. Define f(x, y) as the minimum possible path weight of a path from vertex x to vertex y.

You are given two sequences of length K: (A_1, A_2, \ldots, A_K) and (B_1, B_2, \ldots, B_K). It is guaranteed that A_i \neq B_j (1 \leq i,j \leq K).

Permute the sequence B freely so that \displaystyle \sum_{i=1}^{K} f(A_i, B_i) is minimized.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq \min(\frac{N \times (N-1)}{2},2 \times 10^5)
• 1 \leq K \leq N
• 1 \leq u_i<v_i \leq N (1 \leq i \leq M)
• 1 \leq w_i \leq 10^9
• 1 \leq A_i,B_i \leq N (1 \leq i \leq K)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

8

If we rearrange B as (2,4,4):

• f(1,2) = 5: The path from vertex 1 to vertex 2 passing through vertex 4 contains edge 3 with a maximum edge weight of 5. There is no path with a maximum edge weight less than or equal to 4, so 5 is the minimum possible.
• f(1,4) = 2: The path from vertex 1 to vertex 4 passing through vertex 3 contains edge 1 with a maximum edge weight of 2. There is no path with a maximum edge weight less than or equal to 1, so 2 is the minimum possible.
• f(3,4) = 1: The path from vertex 3 to vertex 4 passing through the direct edge contains an edge with a maximum edge weight of 1. No path can have a maximum weight 0 or less, so 1 is the minimum possible.

Thus, \displaystyle \sum_{i=1}^{3} f(A_i, B_i) = 5+2+1=8. No permutation of B yields 7 or less, so the answer is 8.

Sample Input 2

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

Sample Output 2

3

Problem Statement

There are integer sequences A, B, C of length M each.

C is represented by integers x_1, \dots, x_N, y_1, \dots, y_N. The first y_1 terms of C are x_1, the subsequent y_2 terms are x_2, \ldots, the last y_N terms are x_N.

B is defined by B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M).

A is defined by A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M).

Find the maximum value among A_1, \dots, A_M.

You will be given T test cases to solve.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• The sum of N in a single file is at most 2 \times 10^5.
• 1 \leq M \leq 10^9
• |x_i| \leq 4 \, (1 \leq i \leq N)
• y_i \gt 0 \, (1 \leq i \leq N)
• \sum_{k = 1}^N y_k = M
• All values in input are integers.

Sample Input 1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

Sample Output 1

4
53910
2000000002000000000

In the first test case, we have:

• C = (-1, -1, 2, 2, 2, -3, -3)
• B = (-1, -2, 0, 2, 4, 1, -2)
• A = (-1, -3, -3, -1, 3, 4, 2)

Thus, the maximum value among A_1, \dots, A_M is 4.