Problem Statement

Takahashi is the manager of a logistics center that oversees N warehouses. Each warehouse has an upper limit on its storage capacity.

Each warehouse i (1 \leq i \leq N) currently stores W_i kilograms of goods, and its capacity limit is L_i kilograms. It is not necessarily the case that W_i \leq L_i in the initial state; there may be warehouses that already exceed their capacity limit.

A total of M loading/unloading operations will be performed in order. In the j-th operation (1 \leq j \leq M), a change of C_j kilograms occurs at warehouse P_j. If C_j is positive, it represents loading (goods increase); if C_j is negative, it represents unloading (goods decrease); if C_j = 0, it means no change. Multiple operations may be performed on the same warehouse.

Even if the amount of goods in a warehouse exceeds its capacity limit or becomes negative during or after the operations, the operations continue without interruption. Even if the final amount of goods is negative, the overcapacity check is performed as usual.

After all operations are completed, determine the number of warehouses that are over capacity. Warehouse i is over capacity if the final amount of goods in warehouse i is strictly greater than L_i (if it equals L_i, it is not over capacity). The determination is based solely on the final amount of goods after all operations are completed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 0 \leq W_i \leq 10^9
• 1 \leq L_i \leq 10^9
• It is possible that W_i > L_i
• 1 \leq P_j \leq N
• -10^9 \leq C_j \leq 10^9 (including the case C_j = 0)
• All input values are integers

Sample Input 1

3 4
50 100
80 100
30 50
1 30
2 25
3 15
2 10

Sample Output 1

1

Sample Input 2

5 6
100 200
150 150
0 100
200 300
50 80
2 10
3 50
5 20
1 150
3 60
5 15

Sample Output 2

4

Sample Input 3

10 12
500000000 1000000000
999999999 1000000000
0 100
750000000 800000000
100 100
0 1000000000
123456789 500000000
999999998 999999999
50 50
1000000000 1000000000
1 500000001
2 2
4 100000000
5 1
9 1
7 400000000
3 -50
8 5
6 1000000000
10 1
3 200
4 -50000000

Sample Output 3

8

Problem Statement

Takahashi wants to purchase all N items written on his shopping list, buying exactly 1 of each.

The i-th item (1 \leq i \leq N) on the shopping list belongs to category T_i. Note that the shopping list may contain multiple items of the same category.

There are M shops in total where items can be purchased. The j-th shop (1 \leq j \leq M) sells only items of category S_j, at a price of C_j yen per item. Multiple shops may sell items of the same category. Each shop has unlimited stock, so any number of items can be purchased from it.

For each item on the shopping list, Takahashi chooses exactly one shop that handles that item's category to purchase it from. Even for items of the same category, he may choose a different shop for each item, or he may choose the same shop repeatedly.

If there exists even one category on the shopping list that is not handled by any shop, it is impossible to purchase all items.

Determine whether it is possible to purchase all items, and if so, output the minimum total purchase cost. Here, the total purchase cost is the sum of the prices at the chosen shops for each of the N items on the shopping list.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq T_i \leq 10^9
• 1 \leq S_j \leq 10^9
• 1 \leq C_j \leq 10^9
• All inputs are integers.
• It is guaranteed that the answer is at most 2 \times 10^{14} (when purchasing is possible).

Sample Input 1

3 3
1 2 1
1 100
1 150
2 200

Sample Output 1

400

Sample Input 2

3 2
1 2 3
1 100
2 200

Sample Output 2

-1

Sample Input 3

8 7
5 1000000000 5 3 1000000000 3 5 3
5 500
5 300
1000000000 1000000000
1000000000 999999999
3 700
3 600
3 800

Sample Output 3

2000002698

Problem Statement

You are given a maze on an N \times N grid. The cell at the i-th row from the top and the j-th column from the left is denoted as (i, j). Each cell contains one of the following characters: ., #, S, or G. . represents a passable empty cell, # represents a wall (an impassable cell), S represents the start position, and G represents the goal position. The cells S and G are also passable.

Takahashi wants to move from the start position S to the goal position G. From his current cell, Takahashi can move in one step to an adjacent cell in one of the four directions (up, down, left, right). However, he cannot move outside the grid or into a wall cell.

Find the minimum number of cells on the path from the start position to the goal position (including the start position and the goal position).

Constraints

• 2 \leq N \leq 500
• N is an integer
• The string c_i (1 \leq i \leq N) representing the i-th row of the grid is a string of length N consisting of ., #, S, and G
• Exactly one S exists in the entire grid
• Exactly one G exists in the entire grid
• It is guaranteed that the goal position G is reachable from the start position S

Sample Input 1

4
S...
.#..
..#G
....

Sample Output 1

6

Sample Input 2

3
S#.
.#G
...

Sample Output 2

6

Sample Input 3

8
S..#....
##.#.##.
...#...#
.#####.#
.....#.G
.###.#..
...#....
.#......

Sample Output 3

20

Sample Input 4

15
S..............
.#############.
.............#.
.###########.#.
.#.........#.#.
.#.#######.#.#.
.#.#.....#.#.#.
.#.#.###.#.#.#.
.#.#.#G#.#.#.#.
.#.#.#...#.#.#.
.#.#.#####.#.#.
.#.#.......#.#.
.#.#########.#.
.#...........#.
...............

Sample Output 4

63

Sample Input 5

2
SG
..

Sample Output 5

2

Problem Statement

A certain museum has several rooms, each displaying a sequence of black and white tiles of length N. The display in each room is represented by a binary string of length N, where 0 means a white tile and 1 means a black tile. However, strings in which the same character appears 3 or more times consecutively are not adopted for aesthetic reasons, and no such rooms exist.

All strings satisfying the condition are sorted in lexicographic order, and room numbers 1, 2, 3, \ldots are assigned from the beginning. In lexicographic order, 0 is considered smaller than 1.

When the displays of two rooms differ in exactly 1 position (that is, flipping one character of one string yields the other string), those two rooms are directly connected by a corridor. Corridors are bidirectional, and one can move from either of the two connected rooms to the other. Note that if flipping one character results in a string that does not satisfy the condition (the same character appears 3 or more times consecutively), the room corresponding to that string does not exist, so no corridor exists either.

Takahashi begins his tour from the room corresponding to string s. The starting room is considered visited at the beginning of the tour. After that, he repeats the following operation:

• If there exists one or more unvisited rooms directly connected to the current room by a corridor, move to the room with the smallest room number among them, and mark that room as visited.
• If no such room exists, end the tour. He does not backtrack to previously visited rooms to continue exploration.

Determine after how many moves the room corresponding to string t is first visited. The starting point counts as after 0 moves (if s = t, output 0). If the tour ends without visiting the room corresponding to string t, output -1.

Constraints

• 1 \leq N \leq 26
• s is a string of length N consisting of 0 and 1
• t is a string of length N consisting of 0 and 1
• s does not contain the same character appearing 3 or more times consecutively
• t does not contain the same character appearing 3 or more times consecutively

Sample Input 1

3
001
100

Sample Output 1

4

Sample Input 2

4
0010
1010

Sample Output 2

-1

Sample Input 3

12
010110010110
110100110100

Sample Output 3

-1

Sample Input 4

26
00110011001100110011001100
01010101010101010101010101

Sample Output 4

-1

Sample Input 5

1
0
0

Sample Output 5

0

Problem Statement

Takahashi is trying to authenticate by sending a password to N agents.

The password is a sequence of length L consisting of integers between 1 and K inclusive: S = (S_1, S_2, \dots, S_L).

Takahashi has a faded memo, which can be read as a sequence of length L: B = (B_1, B_2, \dots, B_L). Here,

• If B_j = 0, it means the value at that position could not be read, and S_j can be set to any integer between 1 and K inclusive.
• If B_j \neq 0, then S_j = B_j must hold.

Before starting the transmission, Takahashi fills in all undetermined positions to complete the password S. Each position can independently be assigned any integer between 1 and K inclusive (the same value may be used at different positions). Once completed, S cannot be changed afterwards.

For transmission, a single cipher device is used. This device holds a conversion rule as a permutation C = (C_1, C_2, \dots, C_K) on \{1, 2, \dots, K\}. Initially, C is the identity permutation, i.e., C_x = x for all x (1 \leq x \leq K).

After completing the password, Takahashi transmits it to all N agents exactly once each, in an order he chooses. When transmitting to agent i, the following operations are performed in this order:

1. Transmission and authentication check: Using the device's current conversion rule C, each element of the password S is encrypted and sent. Specifically, the sequence received by agent i is (C_{S_1}, C_{S_2}, \dots, C_{S_L}). If this sequence exactly matches agent i's authentication code T_i = (T_{i,1}, T_{i,2}, \dots, T_{i,L}), then agent i's authentication succeeds.
2. Conversion rule update: Regardless of whether authentication succeeded or not, the device's conversion rule is updated using agent i's permutation A_i = (A_{i,1}, A_{i,2}, \dots, A_{i,K}). The new conversion rule C' is defined for all x (1 \leq x \leq K) by

C'_x = A_{i, C_x}

(i.e., it is replaced by the composition A_i \circ C).

Takahashi is free to choose both how to complete the password S and the order of transmission to the N agents.

Find the maximum number of agents whose authentication can succeed when both choices are made optimally. Furthermore, among all completed passwords S that achieve this maximum, find the lexicographically smallest one. Here, "achieves the maximum" means that there exists some transmission order under which the number of agents whose authentication succeeds equals the maximum.

For two sequences U and V of length L, if U \neq V, let j be the first position where they differ; then U is lexicographically smaller than V if U_j < V_j.

Constraints

• 1 \leq N \leq 8
• 1 \leq K \leq 8
• 1 \leq L \leq 200
• 0 \leq B_j \leq K (1 \leq j \leq L)
• 1 \leq T_{i,j} \leq K (1 \leq i \leq N, 1 \leq j \leq L)
• 1 \leq A_{i,k} \leq K (1 \leq i \leq N, 1 \leq k \leq K)
• A_i is a permutation of \{1, 2, \dots, K\} (contains each integer from 1 to K exactly once)
• All input values are integers

Sample Input 1

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

Sample Output 1

2
1 2 3 1

Sample Input 2

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

Sample Output 2

1
1 1 1 2 2

Sample Input 3

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

Sample Output 3

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

Sample Input 4

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

Sample Output 4

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

Sample Input 5

1 1 1
0
1
1

Sample Output 5

1
1