Problem Statement

Takahashi has N friends. They have nicknames: Friend 1, Friend 2, \ldots, Friend N.

One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1, 2, \ldots, N, when Friend i learns the secret, he/she will share it with Friend A_i, if Friend A_i has not already learned it.

How many of Takahashi's friends will learn the secret in the end?

Constraints

• 2 \leq N \leq 10^5
• 1 \leq X \leq N
• 1 \leq A_i \leq N
• A_i \neq i
• All values in input are integers.

Sample Input 1

4 2
3 1 1 2

Sample Output 1

3

Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.

• One day, Takahashi let Friend 2 learn the secret.
• Friend 2 shares it with Friend 1.
• Friend 1 shares it with Friend 3.

In the end, three of his friends learn the secret, so we print 3.

Sample Input 2

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

Sample Output 2

7

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

If S_{i,j} is #, the cell (i,j) is impassable; if it is ., the cell is passable and contains no house; if it is @, the cell is passable and contains a house.

Initially, Santa Claus is in cell (X,Y). He will act according to the string T as follows.

• Let |T| be the length of the string T. For i=1,2,\ldots,|T|, he moves as follows.
  • Let (x,y) be the cell he is currently in.
    • If T_i is U and cell (x-1,y) is passable, move to cell (x-1,y).
    • If T_i is D and cell (x+1,y) is passable, move to cell (x+1,y).
    • If T_i is L and cell (x,y-1) is passable, move to cell (x,y-1).
    • If T_i is R and cell (x,y+1) is passable, move to cell (x,y+1).
    • Otherwise, stay in cell (x,y).

Find the cell where he is after completing all actions, and the number of distinct houses that he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

• 3 \leq H,W \leq 100
• 1 \leq X \leq H
• 1 \leq Y \leq W
• All given numbers are integers.
• Each S_{i,j} is one of #, ., @.
• S_{i,1} and S_{i,W} are # for every 1 \leq i \leq H.
• S_{1,j} and S_{H,j} are # for every 1 \leq j \leq W.
• S_{X,Y}= .
• T is a string of length at least 1 and at most 10^4, consisting of U, D, L, R.

Sample Input 1

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

Sample Output 1

2 3 1

Santa Claus behaves as follows:

• T_1= L, so he moves from (3,4) to (3,3). A house is passed.
• T_2= L, so he moves from (3,3) to (3,2).
• T_3= L, but cell (3,1) is impassable, so he stays at (3,2).
• T_4= D, so he moves from (3,2) to (4,2).
• T_5= R, so he moves from (4,2) to (4,3).
• T_6= U, so he moves from (4,3) to (3,3). A house is passed, but it has already been passed.
• T_7= U, so he moves from (3,3) to (2,3).

The number of houses he passed or arrived during his actions is 1.

Sample Input 2

6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR

Sample Output 2

3 11 11

Sample Input 3

12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

Sample Output 3

4 14 1

Problem Statement

There are N boxes numbered 1 to N and N items numbered 1 to N. Item i (1 \leq i \leq N) is in box A_i and has a weight of W_i.

You can repeatedly perform the operation of choosing an item and moving it to another box zero or more times. If the weight of the item being moved is w, the cost of the operation is w.

Find the minimum total cost required to make each box contain exactly one item.

Constraints

• 1 \leq N \leq 10^{5}
• 1 \leq A_i \leq N (1 \leq i \leq N)
• 1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
2 2 3 3 5
33 40 2 12 16

Sample Output 1

35

With the following two moves, you can make each box contain exactly one item:

• Move item 1 from box 2 to box 1. The cost is 33.
• Move item 3 from box 3 to box 4. The cost is 2.

The total cost of these two moves is 35. It is impossible to make each box contain exactly one item with a cost less than 35, so print 35.

Sample Input 2

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

Sample Output 2

17254

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq M \leq 7
• 1 \leq B_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes

Problem Statement

In the country of AtCoder there are N zoos, numbered 1 to N. The admission fee for zoo i is C_i yen.

Mr. Suzuki likes M kinds of animals, animals 1,\dots,M.
Animal i can be seen at K_i zoos, namely zoos A_{i,1},\dots,A_{i,K_i}.

Find the minimum total admission fee required to see all M kinds of animals at least twice each.
If you visit the same zoo multiple times, the animals there are considered seen once per every visit.

Constraints

• 1 \le N \le 10
• 1 \le M \le 100
• 0 \le C_i \le 10^9
• 1 \le K_i \le N
• 1 \le A_{i,j} \le N
• j \neq j' \Longrightarrow A_{i,j} \neq A_{i,j'}
• All input values are integers.

Sample Input 1

4 3
1000 300 700 200
3 1 3 4
3 1 2 4
2 1 3

Sample Output 1

1800

For example, the following schedule achieves seeing animals 1,2,3 at least twice each for a total of 1800 yen:

• Go to zoo 3. Pay 700 yen and see animals 1 and 3.
• Go to zoo 3. Pay 700 yen and see animals 1 and 3.
• Go to zoo 4. Pay 200 yen and see animals 1 and 2.
• Go to zoo 4. Pay 200 yen and see animals 1 and 2.

Sample Input 2

7 6
500 500 500 500 500 500 1000
3 1 2 7
3 2 3 7
3 3 4 7
3 4 5 7
3 5 6 7
3 6 1 7

Sample Output 2

2000

By visiting zoo 7 twice, you can see animals 1,2,3,4,5,6 twice each for a total of 2000 yen.