Problem Statement

Takahashi purchased lottery tickets.

Today is the day of the winning number announcement. K distinct positive integers A_1, A_2, \ldots, A_K were announced as the winning numbers. Takahashi has M lottery tickets, and each ticket has one number (a positive integer) written on it. Letting B_1, B_2, \ldots, B_M denote the numbers written on Takahashi's lottery tickets in order, these are all distinct from each other.

Find the number of Takahashi's lottery tickets that have a number matching one of the winning numbers.

Constraints

• 1 \leq K \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq K)
• 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
• A_1, A_2, \ldots, A_K are all distinct
• B_1, B_2, \ldots, B_M are all distinct
• All inputs are integers

Sample Input 1

5 3
1 2 3 4 5
2 7 4

Sample Output 1

2

Sample Input 2

4 6
100 200 300 400
150 200 250 300 350 400

Sample Output 2

3

Sample Input 3

10 8
1000000000 999999999 123456789 987654321 555555555 111111111 222222222 333333333 444444444 666666666
123456789 100000000 555555555 777777777 888888888 999999999 12345 67890

Sample Output 3

3

Problem Statement

Takahashi has placed N cards on a table. Each card has a front side and a back side, each with an integer written on it. The front side of the i-th card has the integer F_i, and the back side has the integer B_i. Initially, all cards are placed with their front side facing up.

Takahashi can choose exactly K distinct cards from these N cards and flip them over (so that their back side faces up). The remaining cards that are not flipped stay with their front side facing up.

Find the maximum possible value of the sum of the integers written on the face-up sides of all the cards.

Constraints

• 1 \leq N \leq 20
• 0 \leq K \leq N
• 1 \leq F_i \leq 100
• 1 \leq B_i \leq 100
• All input values are integers

Sample Input 1

3 1
1 5
3 2
4 1

Sample Output 1

12

Sample Input 2

3 0
2 5
3 1
4 3

Sample Output 2

9

Sample Input 3

8 3
10 20
15 5
8 12
6 6
20 25
3 1
7 18
9 4

Sample Output 3

104

Sample Input 4

15 5
12 30
25 10
8 15
50 45
33 40
19 2
7 55
44 44
16 28
5 90
61 20
38 42
14 9
27 35
10 10

Sample Output 4

540

Sample Input 5

1 1
3 7

Sample Output 5

7

Problem Statement

Takahashi is in charge of running a flea market at a school festival. The flea market has N vendor booths, numbered from 1 to N.

The booths are arranged on a straight line. Booth i (1 \leq i \leq N) has coordinate X_i and attractiveness S_i.

As a festival event, nearby booths will conduct collaboration sales with each other. Specifically, for a pair of two distinct booths (i, j) (1 \leq i < j \leq N), if the absolute difference in their coordinates |X_i - X_j| is at most D, customers can easily go back and forth between both booths, so the collaboration is established. If |X_i - X_j| is greater than D, the collaboration is not established.

The "synergy" of a pair where collaboration is established is defined as the product of the attractiveness values of the two booths: S_i \times S_j.

Takahashi wants to find the total sum of synergy over all pairs where collaboration is established.

Given the coordinate and attractiveness of each of the N booths, find the sum of the synergy S_i \times S_j over all pairs of booths (i, j) (1 \leq i < j \leq N) where collaboration is established.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq D \leq 10^9
• 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq S_i \leq 10^4 (1 \leq i \leq N)
• All X_i are distinct
• All input values are integers
• It is guaranteed that the answer (the total sum of synergy) is at most 2^{63} - 1

Sample Input 1

3 3
1 2
3 3
7 4

Sample Output 1

6

Sample Input 2

4 10
1 1
2 2
5 3
8 4

Sample Output 2

35

Sample Input 3

8 5
0 3
2 7
4 1
8 5
10 2
15 6
17 4
20 8

Sample Output 3

162

Sample Input 4

15 100
10 50
200 30
350 80
500 20
610 90
750 40
880 60
1000 10
1050 70
1200 100
1350 25
1500 55
1600 35
1700 45
1800 15

Sample Output 4

4875

Sample Input 5

1 1000000000
500000000 10000

Sample Output 5

0

Problem Statement

Takahashi works at a delivery company. Today, Takahashi received N delivery requests.

The delivery area consists of M bases numbered from 1 to M, connected by K bidirectional roads. The j-th road (1 \leq j \leq K) connects base U_j and base V_j, and has length W_j.

For the i-th delivery request (1 \leq i \leq N), a package must be delivered from the departure base S_i to the destination base T_i. For each delivery request, find the shortest distance from the departure base to the destination base (the minimum total length of roads traversed), and calculate the sum of the shortest distances for all N requests.

It is guaranteed that for every delivery request, the destination base is reachable from the departure base by following roads.

Constraints

• 1 \leq N \leq 10^5
• 2 \leq M \leq 200
• 1 \leq K \leq \frac{M(M-1)}{2}
• 1 \leq U_j < V_j \leq M (1 \leq j \leq K)
• 1 \leq W_j \leq 10^6 (1 \leq j \leq K)
• There is at most one road connecting any pair of bases (i.e., all pairs (U_j, V_j) are distinct)
• 1 \leq S_i \leq M (1 \leq i \leq N)
• 1 \leq T_i \leq M (1 \leq i \leq N)
• S_i \neq T_i (1 \leq i \leq N)
• For every delivery request, T_i is reachable from S_i
• All input values are integers

Sample Input 1

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

Sample Output 1

11

Sample Input 2

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

Sample Output 2

25

Sample Input 3

5 6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9
1 5
2 6
3 4
6 4
1 4

Sample Output 3

76

Problem Statement

Takahashi is in charge of planning the city's snow removal operations. The city has N intersections, numbered from 1 to N. The intersections are connected by M roads, each of which is passable in both directions. There may be multiple roads connecting the same pair of vertices, but they are treated as distinct roads. The i-th road connects intersection U_i and intersection V_i, and it takes W_i minutes for the snow plow to traverse it in either direction.

Takahashi must plan a route for the snow plow that starts from the depot at intersection 1, traverses each of the M roads at least once, and finally returns to the depot at intersection 1. A road is considered cleared of snow once it is traversed in either one direction; it is not necessary to traverse it in both directions. The snow plow may traverse the same road more than once, regardless of whether it is in the same or opposite direction. It is also allowed to pass through intersection 1 any number of times during the route. Since fuel is limited, Takahashi wants to complete the patrol in as short a time as possible.

Find the minimum total travel time (in minutes) required for the snow plow to depart from intersection 1, traverse every road at least once, and return to intersection 1.

It is guaranteed that the given graph is connected.

Constraints

• 2 \leq N \leq 10^5
• N - 1 \leq M \leq 10^5
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• 1 \leq W_i \leq 10^6
• The graph is connected
• The number of vertices with odd degree is at most 16. Here, the degree of a vertex is the number of edges incident to it, where each edge of a multi-edge is counted separately
• There may be multiple roads connecting the same pair of vertices (multi-edges may exist)
• All input values are integers

Sample Input 1

3 3
1 2 4
2 3 5
3 1 6

Sample Output 1

15

Sample Input 2

3 2
1 2 3
2 3 5

Sample Output 2

16

Sample Input 3

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

Sample Output 3

48

Sample Input 4

15 20
1 2 10
2 3 8
3 4 7
4 5 12
5 6 3
6 7 9
7 8 5
8 9 11
9 10 6
10 11 4
11 12 8
12 13 7
13 14 13
14 15 2
15 1 14
1 8 20
3 10 15
5 12 6
7 14 9
2 9 18

Sample Output 4

228

Sample Input 5

2 1
1 2 1000000

Sample Output 5

2000000