Problem Statement

Takahashi has an integer sequence of length N: A = (A_1, A_2, \dots, A_N), and Aoki has an integer sequence of the same length N: B = (B_1, B_2, \dots, B_N).

Takahashi and Aoki want to make their two integer sequences match element by element. To achieve this, they can perform the following operation any number of times. The same index may be chosen multiple times.

In one operation, choose an index i (1 \leq i \leq N) and perform exactly one of the following four actions:

• Increase the value of A_i by 1
• Decrease the value of A_i by 1
• Increase the value of B_i by 1
• Decrease the value of B_i by 1

Find the minimum number of operations required to reach a state where A_i = B_i for all i (1 \leq i \leq N).

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
• -10^9 \leq B_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers.

Sample Input 1

3
1 3 5
2 1 5

Sample Output 1

3

Sample Input 2

5
3 -1 0 7 -5
-2 4 0 10 -5

Sample Output 2

13

Sample Input 3

8
1000000000 -999999999 500000000 0 -100 42 -7 123456789
-1000000000 999999999 -500000000 0 200 -58 7 -987654321

Sample Output 3

6111111522

Problem Statement

Takahashi manages N orchards.

Orchard i (1 \le i \le N) currently has A_i fruits growing on its trees.

Starting from tomorrow, Takahashi will perform harvesting work over K days, choosing exactly 1 orchard each day. He may choose the same orchard on multiple days, and he is also allowed to choose an orchard with 0 fruits.

When harvesting work is performed at orchard i for one day, Takahashi can harvest a number of fruits equal to the smaller of the number of fruits currently remaining in that orchard and B_i. In other words, if there are r fruits remaining in the orchard before the work, he harvests \min(r, B_i) fruits, and the remaining number of fruits becomes r - \min(r, B_i).

No new fruits grow, and the number of fruits in each orchard only decreases through harvesting.

When Takahashi optimally chooses which orchards to work at over the K days, find the maximum total number of fruits he can harvest.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{18}
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

3 4
5 2
3 5
10 4

Sample Output 1

13

Sample Input 2

2 7
4 3
2 1

Sample Output 2

6

Sample Input 3

8 15
12 3
7 10
25 4
9 2
14 7
30 6
5 1
18 5

Sample Output 3

82

Sample Input 4

20 60
45 6
120 15
78 9
33 4
200 25
17 3
96 8
150 20
64 7
89 11
210 30
58 5
132 12
41 10
73 6
185 18
27 2
99 13
160 16
52 14

Sample Output 4

1143

Sample Input 5

1 1000000000000000000
1000000000 1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi loves card games and places cards with numbers written on them by stacking them on a desk.

Each card has a positive integer written on it. Takahashi builds a pile by stacking cards. When placing a new card, he puts it on top of the pile, and when removing a card, he can only take the topmost one (the one placed most recently). Removed cards are discarded and are not involved in any subsequent operations.

Initially, the pile contains no cards. Takahashi performs N operations in order. Each operation is one of the following three types:

• Put operation PUT c: Place a card with the positive integer c written on it on top of the pile.
• Remove operation REMOVE: Remove the topmost card from the pile and discard it. It is guaranteed that the pile contains at least one card when this operation is performed.
• Look operation LOOK: Compute the bitwise XOR (exclusive or) of the numbers written on all cards currently in the pile. It is guaranteed that the pile contains at least one card when this operation is performed. If the pile contains exactly one card, the XOR value is the number written on that card itself.

Extract only the look operations from the N operations in the order they appear, and number them 1, 2, 3, \ldots, K (where K is the total number of look operations). Let v_i be the XOR value obtained by the i-th look operation.

For each i = 1, 2, \ldots, K, find the largest integer j such that v_j = v_i and j < i. In other words, find the number of the most recent past look operation that yielded the same XOR value as the i-th look operation. If no such j exists, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• The value c given in each put operation satisfies 1 \leq c \leq 10^9.
• When a REMOVE operation is performed, the pile contains at least one card.
• When a LOOK operation is performed, the pile contains at least one card.
• Among the N operations, at least one LOOK operation is included (i.e., K \geq 1).
• All numerical values given in the input are integers.

Sample Input 1

7
PUT 3
PUT 5
LOOK
PUT 6
LOOK
REMOVE
LOOK

Sample Output 1

-1
-1
1

Sample Input 2

6
PUT 1
LOOK
PUT 2
LOOK
PUT 4
LOOK

Sample Output 2

-1
-1
-1

Sample Input 3

15
PUT 10
PUT 7
LOOK
REMOVE
LOOK
PUT 3
LOOK
PUT 9
LOOK
REMOVE
REMOVE
LOOK
PUT 5
LOOK
REMOVE

Sample Output 3

-1
-1
-1
-1
2
-1

Sample Input 4

24
PUT 1
PUT 2
PUT 4
LOOK
REMOVE
LOOK
REMOVE
LOOK
PUT 8
LOOK
PUT 6
LOOK
REMOVE
LOOK
REMOVE
LOOK
PUT 3
LOOK
PUT 2
LOOK
REMOVE
LOOK
REMOVE
LOOK

Sample Output 4

-1
-1
-1
-1
-1
4
3
-1
-1
8
7

Sample Input 5

2
PUT 1000000000
LOOK

Sample Output 5

-1

Problem Statement

Takahashi is strolling through the streets of a city. The city has N intersections, and the intersections are connected by bidirectional roads. There are M roads in total, and each road has a required travel time. Multiple roads may connect the same pair of intersections, but there are no roads connecting an intersection to itself (no self-loops).

The city has K toll gates, each installed at a distinct intersection. The j-th toll gate is installed at intersection L_j, and its toll fee is C_j. No toll fee is charged at intersections without a toll gate.

Takahashi wants to travel from intersection 1 to intersection N. He moves from intersection to intersection via roads, and he may pass through the same intersection or the same road multiple times.

Takahashi's route is represented as a sequence of intersections v_0, v_1, v_2, \ldots, v_s (where v_0 = 1 and v_s = N). Here, each pair of consecutive intersections v_{k-1} and v_k (1 \leq k \leq s) must be directly connected by a road.

The total cost of the trip is the sum of the following two components:

• The total travel time of the roads traversed. That is, the sum of the travel times of the roads chosen to connect v_{k-1} and v_k for k = 1, 2, \ldots, s. If the same road is traversed multiple times, it is counted that many times.
• The total toll fees at toll gates located at intersections along the route. That is, for each intersection in v_0, v_1, \ldots, v_s, if that intersection has a toll gate, its toll fee is added. If the same intersection appears multiple times in the route, the fee is charged each time. Both the starting point (intersection 1) and the destination (intersection N) are included.

Find the minimum total cost for Takahashi to travel from intersection 1 to intersection N. It is guaranteed that intersection N is reachable from intersection 1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 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)
• 1 \leq L_j \leq N (1 \leq j \leq K)
• All L_j are distinct (1 \leq j \leq K)
• 1 \leq C_j \leq 10^9 (1 \leq j \leq K)
• Intersection N is reachable from intersection 1
• All input values are integers

Sample Input 1

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

Sample Output 1

10

Sample Input 2

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

Sample Output 2

15

Sample Input 3

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

Sample Output 3

26

Problem Statement

Takahashi is the manager responsible for M facilities. To assign security to all facilities, he plans to select and contract with some of the N security companies.

Each security company i (1 \leq i \leq N) has a contract cost C_i. Additionally, a value E_{i,j} is given that indicates whether security company i can guard facility j. When E_{i,j} = 1, security company i can guard facility j, and when E_{i,j} = 0, it cannot.

Takahashi selects 1 or more companies from the N companies to contract with. However, the same company cannot be selected more than once. Let S be the set of selected security companies. For every facility j (1 \leq j \leq M), there must be at least one company in S that can guard facility j.

Among all ways of choosing S that satisfy this condition, find the minimum total contract cost \displaystyle\sum_{i \in S} C_i. If no valid selection exists, output -1.

Constraints

• 1 \leq N \leq 50
• 1 \leq M \leq 18
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
• E_{i,j} \in \{0, 1\} (1 \leq i \leq N, 1 \leq j \leq M)
• All input values are integers

Sample Input 1

4 3
4 6 5 11
1 1 0
0 1 1
1 0 0
1 1 1

Sample Output 1

10

Sample Input 2

4 4
5 2 7 4
1 0 0 0
0 1 1 0
1 0 1 0
0 1 0 0

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

13

Sample Input 4

12 10
14 9 20 11 8 7 13 6 15 10 12 5
1 0 1 0 0 1 0 0 0 0
0 1 0 1 0 0 1 0 0 0
1 1 0 0 1 0 0 1 0 0
0 0 1 1 0 1 0 0 1 0
1 0 0 0 1 0 1 0 0 1
0 1 1 0 0 0 0 1 1 0
0 0 0 1 1 1 0 0 0 1
1 0 0 0 0 0 1 1 0 0
0 1 0 1 0 1 0 1 0 1
0 0 1 0 1 0 1 0 1 0
1 0 0 1 0 0 1 0 1 0
0 1 0 0 1 0 0 1 0 1

Sample Output 4

22

Sample Input 5

1 1
1000000000
1

Sample Output 5

1000000000