Problem Statement

Takahashi is an accountant at a company. This company has N part-time staff members, each numbered from 1 to N.

In a certain month, staff member i worked C_i shifts.

The company pays each staff member a base pay of P yen per shift. However, for staff members whose monthly shift count is K or more, a special bonus of B yen per shift is added on top of the base pay for all of that staff member's shifts. In other words, staff members with K or more monthly shifts are paid a total of P + B yen per shift, while staff members with fewer than K shifts are paid P yen per shift.

Find the total salary to be paid to all N staff members.

Constraints

• 1 \leq N \leq 100
• 1 \leq P \leq 1000
• 1 \leq B \leq 1000
• 1 \leq K \leq 31
• 1 \leq C_i \leq 31 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

3 100 50 3
5 2 3

Sample Output 1

1400

Sample Input 2

3 200 100 10
3 5 2

Sample Output 2

2000

Sample Input 3

10 500 300 15
20 10 15 8 25 14 16 5 30 12

Sample Output 3

109300

Sample Input 4

20 1000 500 20
25 18 31 20 10 15 22 28 19 30 5 12 21 27 16 8 24 31 14 20

Sample Output 4

535500

Sample Input 5

1 1 1 1
1

Sample Output 5

2

Problem Statement

Takahashi is in charge of warehouse management at a logistics center.

The logistics center has N warehouses, each numbered from 1 to N. Initially, warehouse i (1 \leq i \leq N) stores exactly one item with weight V_i.

Aoki is in charge of delivery and gives Q instructions to Takahashi in order. Each instruction is one of the following two types:

• Type 1: "Move all items in warehouse a to warehouse b" (a \neq b). All items currently in warehouse a are moved to warehouse b. After the move, warehouse a becomes empty. Warehouse b will then store both the items it originally had and the items moved from warehouse a. If warehouse a is empty, nothing happens.
• Type 2: "Report the total weight of items in warehouse c". Output the total weight of all items currently stored in warehouse c. If warehouse c is empty, output 0.

Takahashi processes the instructions in order starting from the first. For each Type 2 instruction, determine the value that should be output.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• Each instruction is either Type 1 or Type 2
• For Type 1 instructions, 1 \leq a \leq N, 1 \leq b \leq N, a \neq b
• For Type 2 instructions, 1 \leq c \leq N
• All input values are integers

Sample Input 1

3 5
10 20 30
1 1 2
2 2
2 1
1 3 2
2 2

Sample Output 1

30
0
60

Sample Input 2

4 6
5 15 25 35
2 4
1 1 3
1 2 3
2 3
1 1 4
2 1

Sample Output 2

35
45
0

Sample Input 3

8 12
100 200 300 400 500 600 700 800
1 1 2
1 3 2
2 2
1 4 5
1 6 5
2 5
1 2 5
2 5
1 7 8
1 8 5
2 5
2 7

Sample Output 3

600
1500
2100
3600
0

Sample Input 4

10 15
1000000000 999999999 888888888 777777777 666666666 555555555 444444444 333333333 222222222 111111111
1 1 2
1 3 2
1 4 2
2 2
1 5 6
1 7 6
1 8 6
2 6
1 2 10
1 6 10
2 10
1 9 10
2 10
2 1
2 5

Sample Output 4

3666666664
1999999998
5777777773
5999999995
0
0

Sample Input 5

1 1
1000000000
2 1

Sample Output 5

1000000000

Problem Statement

Takahashi is preparing for a team programming contest and has decided to select 2 different people from the members to form one pair.

The team has N members, and the i-th member (1 \leq i \leq N) has a positive integer value A_i representing their programming ability. Note that different members may have the same ability value, but as long as they are different people, they can be distinguished and selected for a pair.

The "combined strength" of a pair consisting of the i-th member and the j-th member (1 \leq i < j \leq N) is defined as the sum of their ability values, A_i + A_j.

Takahashi wants to select a pair that maximizes the combined strength.

Find the maximum possible value of the pair's combined strength.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

5
3 1 4 1 5

Sample Output 1

9

Sample Input 2

3
100 200 150

Sample Output 2

350

Sample Input 3

10
500000000 1000000000 250000000 750000000 100000000 999999999 300000000 600000000 400000000 800000000

Sample Output 3

1999999999

Problem Statement

Takahashi is working as a network engineer at a telecommunications company and is in charge of planning the installation of fiber optic cables.

There are N relay stations in the city, numbered from 1 to N. There are also M underground tunnels, each connecting two different relay stations bidirectionally. The i-th tunnel (1 \leq i \leq M) connects relay station U_i and relay station V_i, and has a width of W_i centimeters.

Takahashi wants to install a fiber optic cable bundle of width K centimeters from the data center at relay station 1 to the customer building at relay station N. In order to pass the cable bundle through a tunnel, the width of that tunnel must be at least K centimeters. Therefore, all tunnels along the installation route must have a width of at least K centimeters.

Here, a path from relay station 1 to relay station N is a sequence of relay stations v_0, v_1, \ldots, v_L (L \geq 1) satisfying all of the following conditions:

• v_0 = 1 and v_L = N.
• For each j (1 \leq j \leq L), there exists a tunnel connecting relay station v_{j-1} and relay station v_j.
• v_0, v_1, \ldots, v_L are all distinct (no relay station is visited more than once).

This path passes through L tunnels. We call this L the number of tunnels traversed by the path.

To reduce costs, Takahashi wants to minimize the number of tunnels traversed.

Determine whether there exists a path where all tunnels along the path have a width of at least K centimeters. If such a path exists, output the minimum number of tunnels traversed among all such paths. If no such path exists, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
• 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
• There is at most one tunnel connecting any pair of relay stations
• All input values are integers

Sample Input 1

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

Sample Output 1

3

Sample Input 2

4 4 10
1 2 15
1 3 5
2 3 8
3 4 12

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

3

Problem Statement

Takahashi works as a delivery person. His assigned area has N locations, numbered from location 1 to location N. There are M one-way roads between locations, and the i-th road (1 \leq i \leq M) can only be traversed from location U_i to location V_i, with a positive cost of W_i. Takahashi moves between locations using only these roads.

Takahashi is currently at the office located at location S. As today's task, he needs to deliver packages to K destinations T_1, T_2, \ldots, T_K. These destinations are all distinct from each other and all different from location S.

Takahashi departs from location S, visits all K destinations in any order he likes to deliver the packages, and must finally return to the office at location S. Here, Takahashi's route is a sequence of roads starting from location S, traversing roads one by one (such that the endpoint of each road matches the starting point of the next road), and ultimately arriving back at location S. A package is considered delivered to a destination as long as Takahashi passes through that destination's location at least once during the route from departure to return. That is, merely passing through a destination location is sufficient.

During the journey, it is permitted to traverse the same road or visit the same location multiple times. However, if the same road is traversed multiple times, its cost is incurred each time.

Find the minimum total cost of roads traversed (where the cost of a road traversed multiple times is counted for each traversal) over all possible routes where Takahashi departs from location S, visits all K destinations, and returns to location S. If it is impossible to visit all destinations and return to location S, output -1.

Constraints

• 2 \leq N \leq 300
• 1 \leq M \leq N(N-1)
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• No two roads share the same pair of start and end points (U_i, V_i) (no parallel edges)
• 1 \leq W_i \leq 10^6
• 1 \leq S \leq N
• 1 \leq K \leq 15
• 1 \leq T_j \leq N (1 \leq j \leq K)
• All T_j are distinct
• T_j \neq S (1 \leq j \leq K)
• All input values are integers

Sample Input 1

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

Sample Output 1

9

Sample Input 2

3 2
1 2 1
2 3 1
1 1
2

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

20

Sample Input 4

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

Sample Output 4

43

Sample Input 5

2 2
1 2 1000000
2 1 1000000
1 1
2

Sample Output 5

2000000