Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

• Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

Constraints

• 1\leq N\leq8
• 0\leq M _ G\leq\dfrac{N(N-1)}2
• 0\leq M _ H\leq\dfrac{N(N-1)}2
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
• (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
• 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
• (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
• 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

5
4
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
1 5
3 1 4 1
5 9 2
6 5
3

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

• Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
• Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
• Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
• Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.

Sample Input 2

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

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214

Problem Statement

The AtCoder company office is represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell has a wall; if S_{i,j} is ., that cell is a floor; if S_{i,j} is H, that cell has a humidifier placed on a floor cell.

A certain cell is considered humidified if it can be reached from at least one humidifier cell by at most D moves up, down, left, or right without passing through a wall. Note that any cell with a humidifier is always humidified.

Find the number of humidified floor cells.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• 0 \leq D \leq H\times W
• S_{i,j} is #, ., or H. (1 \leq i \leq H, 1 \leq j \leq W)
• All input numbers are integers.

Sample Input 1

3 4 1
H...
#..H
.#.#

Sample Output 1

5

Five cells (1,1), (1,2), (1,4), (2,3), (2,4) are humidified.

Sample Input 2

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

Sample Output 2

21

Sample Input 3

1 6 3
...#..

Sample Output 3

0

It is possible that no cells are humidified.

Problem Statement

There is a number line, and initially person 0 is standing alone at coordinate 0.

From now on, persons 1,2,\dots,N will arrive in this order and stand on the number line.
Person i stands at coordinate X_i. Here, X_i \ge 1, and X_i is distinct for all persons.

Each time a person arrives, answer the following question.

• Suppose that currently r+1 persons 0,1,\dots,r are standing on the number line.
• Here, define d_i as the distance to the nearest other person from person i.
  • More formally, \displaystyle d_i = \min_{0 \le j \le r, j \neq i} \vert X_i - X_j \vert.
• Find the sum of this d, that is, \displaystyle \sum_{i=0}^r d_i.

Constraints

• All input values are integers.
• 1 \le N \le 5 \times 10^5
• 1 \le X_i \le 10^9
• X_i \neq X_j if i \neq j.

Sample Input 1

10
5 2 7 4 108728325 390529120 597713292 322456626 845148281 812604915

Sample Output 1

10
7
8
8
108728326
390529121
523096670
452057486
699492475
517144218

In this input, 10 persons arrive.
The first four persons are explained below.

• When person 1 arrives, there are persons at coordinates 0,5.
  • The required value is 5+5=10.
• When person 2 arrives, there are persons at coordinates 0,2,5.
  • The required value is 2+2+3=7.
• When person 3 arrives, there are persons at coordinates 0,2,5,7.
  • The required value is 2+2+2+2=8.
• When person 4 arrives, there are persons at coordinates 0,2,4,5,7.
  • The required value is 2+2+1+1+2=8.

Problem Statement

In the nation of Atcoder, there are N cities numbered 1 to N, and M trains numbered 1 to M. Train i departs from city A_i at time S_i and arrives at city B_i at time T_i.

Given a positive integer X_1, find a way to set non-negative integers X_2,\ldots,X_M that satisfies the following condition with the minimum possible value of X_2+\ldots+X_M.

• Condition: For all pairs (i,j) satisfying 1 \leq i,j \leq M, if B_i=A_j and T_i \leq S_j, then T_i+X_i \leq S_j+X_j.
  • In other words, for any pair of trains that are originally possible to transfer between, it is still possible to transfer even after delaying the departure and arrival times of each train i by X_i.

It can be proved that such a way to set X_2,\ldots,X_M with the minimum possible value of X_2+\ldots+X_M is unique.

Constraints

• 2 \leq N \leq 2\times 10^5
• 2 \leq M \leq 2\times 10^5
• 1 \leq A_i,B_i \leq N
• A_i \neq B_i
• 0 \leq S_i < T_i \leq 10^9
• 1 \leq X_1 \leq 10^9
• All input values are integers.

Sample Input 1

3 6 15
1 2 10 20
1 2 20 30
2 3 25 40
2 3 35 50
3 1 15 30
3 1 45 60

Sample Output 1

0 10 0 0 5

The arrival of train 1 from city 1 to 2 is delayed by 15 and becomes time 35.
To allow transfer from train 1 to 3 in city 2, the departure of train 3 is delayed by 10, making it depart at time 35 and arrive at time 50.
Further, to allow transfer from train 3 to 6 in city 3, the departure of train 6 is delayed by 5, making it depart at time 50.
Other trains can operate without delay while still allowing transfers between originally transferable trains, so (X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) satisfies the condition.
Moreover, there is no solution with a smaller sum that satisfies the condition, so this is the answer.

Sample Input 2

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

Sample Output 2

100 100 100 100 100 100 100 100

Sample Input 3

4 4 10
1 2 0 1
1 2 0 10
2 3 100 200
2 4 100 200

Sample Output 3

0 0 0

Problem Statement

There is a circular cake that has been cut into N equal slices by its radii.

Each piece is labeled with an integer from 1 to N in clockwise order, and for each integer i with 1 \leq i \leq N, the piece i is also referred to as piece N + i.

Initially, every piece’s color is color 0.

You can perform the following operation any number of times:

• Choose integers a, b, and c such that 1 \leq a, b, c \leq N. For each integer i with 0 \leq i < b, change the color of piece a + i to color c. The cost of this operation is b + X_c.

You want each piece i (for 1 \leq i \leq N) to have color C_i. Find the minimum total cost of operations needed to achieve this.

Constraints

• 1 \leq N \leq 400
• 1 \leq C_i \leq N
• 1 \leq X_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

20

Let A_i denote the color of piece i. Initially, (A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 0, 0, 0, 0).

Performing an operation with (a, b, c) = (2, 1, 4) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (0, 4, 0, 0, 0, 0).

Performing an operation with (a, b, c) = (3, 3, 2) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (0, 4, 2, 2, 2, 0).

Performing an operation with (a, b, c) = (1, 1, 1) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 2, 2, 0).

Performing an operation with (a, b, c) = (4, 1, 1) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 1, 2, 0).

Performing an operation with (a, b, c) = (6, 1, 5) changes (A_1, A_2, A_3, A_4, A_5, A_6) to (1, 4, 2, 1, 2, 5).

In this case, the total cost is 5 + 5 + 2 + 2 + 6 = 20.

Sample Input 2

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

5000000005

Sample Input 3

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

Sample Output 3

23