Problem Statement

Takahashi is a parking lot manager. The parking lot lies on a straight number line, and the parkable area ranges from coordinate 0 to coordinate M.

Currently, N cars are parked, and the i-th car is at coordinate A_i. However, some cars may have been parked outside the parkable area.

Takahashi needs to move all cars into the parkable area (coordinates between 0 and M, inclusive). Each car can be moved independently of the others, and it costs 1 yen to move one car a distance of 1. That is, the cost of moving a car from coordinate a to coordinate b is |a - b| yen.

Find the minimum total cost required to move all cars into the range of coordinates 0 or greater and M or less.

Note that multiple cars are allowed to occupy the same coordinate, both before and after moving.

Constraints

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

Sample Input 1

3 10
-2 5 12

Sample Output 1

4

Sample Input 2

4 5
0 2 5 3

Sample Output 2

0

Sample Input 3

10 100
-200 -50 -1 0 20 60 99 100 101 150

Sample Output 3

302

Sample Input 4

50 1000
-5000 -1000 -1 0 1 2 10 50 200 500 999 1000 1001 1200 1500 2000 3000 10000 123 456 789 100 900 250 750 333 666 111 222 444 -250 -750 -333 -666 -111 -222 -444 0 1000 -1 1001 500 1500 500000000 -500000000 1000000000 -1000000000 999 1 1002

Sample Output 4

3000019982

Sample Input 5

1 1000000000
-1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is in charge of managing a flower bed arranged in a row. The flower bed has N sections lined up in a row from left to right, and each section either has a flower planted in it or is empty. The i-th section from the left is called section i (1 \leq i \leq N).

The state of the flower bed is represented by a string S of length N. If the i-th character (1 \leq i \leq N) of S is o, then section i has a flower planted in it; if it is ., then section i is empty.

Takahashi waters the flowers using a sprinkler. The sprinkler is fixed at section 1, and he chooses and sets one integer K where 1 \leq K \leq N. When the sprinkler is activated, it sprays water at equally spaced intervals of K starting from section 1. Specifically, the sections that receive water are all sections among 1, 1+K, 1+2K, \ldots whose section numbers are at most N.

If a section that receives water has a flower planted in it, that flower is watered. Nothing happens if water is sprayed on an empty section. Takahashi chooses exactly one value of K and activates the sprinkler exactly once with that setting. He wants to maximize the number of flowers that are watered by optimally choosing the value of K.

Find the maximum number of flowers that can be watered.

Constraints

• 1 \leq N \leq 2 \times 10^5
• S is a string of length N consisting only of o and ..

Sample Input 1

10
o.o.o.o.o.

Sample Output 1

5

Sample Input 2

15
oo.oo.oo.oo.oo.

Sample Output 2

10

Sample Input 3

50
o..o..o..o..o..o..o..o..o..o..o..o..o..o..o..o..o.

Sample Output 3

17

Problem Statement

Takahashi is managing an evacuation drill in a park consisting of N plazas. The plazas are numbered from 1 to N and connected by N-1 paths, forming a tree structure rooted at plaza 1. For each plaza i (2 \leq i \leq N), there is a designated parent plaza P_i, and plaza i and plaza P_i are directly connected by a path.

Each plaza i has a congestion coefficient A_i. Also, there are B_i people at each plaza i.

During the evacuation drill, the B_i people at each plaza i (2 \leq i \leq N) head toward plaza 1, which is the evacuation site. Each person moves along the unique simple path on the tree from plaza i to plaza 1, passing through all plazas on the path including the starting point i and the endpoint 1.

The B_1 people at plaza 1 are already at the evacuation site and do not move, so they do not pass through any plaza.

The congestion of the evacuation drill is defined as the sum, over all moving people, of the total congestion coefficients of all plazas that person passes through. That is,

\text{Congestion} = \sum_{i=2}^{N} B_i \sum_{j \in \mathrm{path}(i,1)} A_j

Here, \mathrm{path}(i,1) denotes the set of plazas on the simple path from plaza i to plaza 1 (including both endpoints).

Find the congestion.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq A_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq P_i < i (2 \leq i \leq N)
• 0 \leq B_i \leq 10^4 (1 \leq i \leq N)
• All input values are integers.
• It is guaranteed that the answer is at most 2^{63}-1.

Sample Input 1

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

Sample Output 1

33

Sample Input 2

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

Sample Output 2

68

Sample Input 3

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

Sample Output 3

267

Sample Input 4

20
4 7 1 3 9 0 2 6 5 8 1 4 7 3 2 9 0 5 6 1
1 1 2 2 3 3 4 4 5 5 6 7 7 8 9 10 11 13 13
3 1 4 0 2 5 1 6 0 3 2 4 1 7 0 2 5 1 3 4

Sample Output 4

811

Sample Input 5

1
10000

10000

Sample Output 5

0

Problem Statement

Takahashi needs to complete all N tasks. Each task is numbered from 1 to N, and each task is executed exactly once, one at a time, in some order.

There are prerequisite conditions between tasks. To execute a certain task, it may be necessary to have completed another task beforehand. There are M such prerequisite conditions given, each expressed in the form "Task A_i must be completed before Task B_i."

Takahashi wants to determine an order to execute all N tasks while satisfying all prerequisite conditions. If such an order exists, find the execution order such that the sequence of task numbers listed in execution order is lexicographically smallest. If the prerequisite conditions are contradictory and it is impossible to execute all tasks, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M
• N + M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• All pairs (A_i, B_i) are distinct
• All input values are integers

Sample Input 1

4 3
1 3
2 3
2 4

Sample Output 1

1 2 3 4

Sample Input 2

3 3
1 2
2 3
3 1

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

1 2 3 4 5 6 7 8

Sample Input 4

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

Sample Output 4

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

Sample Input 5

1 0

Sample Output 5

1

Problem Statement

Takahashi is traveling in a country with N cities numbered from 1 to N. Takahashi is initially in city 1. City 1 is already considered visited from the start.

There are M one-way roads between cities. Using the i-th road, one can travel from city U_i to city V_i in W_i units of time. There may be multiple roads between the same pair of cities. Takahashi may pass through the same city or the same road any number of times.

Takahashi starts from city 1 and travels along roads (he may also choose not to move at all). However, the total travel time of all roads taken must not exceed T. It does not matter which city he ends up in. Any city that has been reached at least once is treated as visited (city 1 is also included as visited).

In this country, K missions are available. The j-th mission is represented by a pair of a set of cities S_j and a reward P_j, meaning "if all cities in S_j have been visited, reward P_j can be obtained." The order of visits does not matter. All missions whose conditions are satisfied can be completed simultaneously, and the total reward earned is the sum of their individual rewards.

Find the maximum total reward that Takahashi can earn. If no mission's condition can be satisfied, the answer is 0.

Constraints

• 2 \leq N \leq 10^4
• 1 \leq M \leq 10^4
• 1 \leq K \leq 100
• 1 \leq T \leq 10^9
• 1 \leq U_i, V_i \leq N
• U_i \neq V_i
• 1 \leq W_i \leq 10^6
• 1 \leq |S_j| \leq 14
• Each element s_{j,k} of S_j satisfies 1 \leq s_{j,k} \leq N
• All elements within each S_j are distinct
• Different missions may have the same set S_j
• The number of elements in \bigcup_{j=1}^{K} S_j is at most 14 (that is, the total number of distinct cities appearing across all missions is at most 14)
• 1 \leq P_j \leq 10^9
• All input values are integers

Sample Input 1

4 4 3 7
1 2 3
2 3 3
1 4 10
3 4 1
1 2 100
2 2 3 300
1 4 500

Sample Output 1

900

Sample Input 2

3 1 2 5
1 2 10
1 2 100
1 3 200

Sample Output 2

0

Sample Input 3

12 18 8 25
1 2 4
1 3 6
2 4 5
3 4 2
4 5 4
2 6 10
5 6 3
6 7 2
7 8 4
3 9 8
9 10 3
10 5 2
8 11 5
11 12 1
5 3 7
6 2 6
4 10 6
10 8 4
1 2 100
2 3 4 250
3 2 5 6 500
2 8 10 700
1 11 900
4 2 4 6 8 1200
2 10 5 400
3 3 9 10 350

Sample Output 3

1850

Sample Input 4

30 50 15 120
1 2 5
1 3 12
1 4 7
2 5 8
2 6 20
3 6 6
4 3 3
4 7 15
5 8 10
6 8 5
6 9 9
7 10 8
8 11 4
9 11 3
10 12 6
11 12 5
12 13 7
13 14 2
14 15 5
15 16 8
16 18 6
13 18 15
18 20 9
20 22 10
22 25 12
25 30 14
12 20 25
8 15 18
5 10 22
3 5 20
2 3 4
11 7 11
15 8 16
18 12 13
20 15 7
22 18 5
25 22 9
30 1 50
9 17 10
17 19 7
19 21 4
21 23 6
23 24 3
24 26 8
26 27 4
27 28 5
28 29 3
29 30 2
10 20 30
6 18 40
1 1 100
1 2 150
2 2 5 400
3 3 8 12 900
2 15 18 1200
4 2 7 10 12 1300
3 20 22 25 2000
1 30 3000
5 1 3 5 8 15 1700
2 18 20 800
3 10 12 20 1100
4 15 20 22 25 1600
2 25 30 2200
6 2 3 5 7 8 10 2500
3 12 18 30 1800

Sample Output 4

14350

Sample Input 5

2 1 1 1
2 1 1000000
1 1 1000000000

Sample Output 5

1000000000