Shark Elementary School

Interview

Time limit1sMemory limit1024 MB

Summary

Seat students one by one in an N x N grid, choosing each seat by liking-adjacency, then empty-adjacency, then row and column, and sum the resulting satisfaction scores.

Level: Medium5 of 10
Topics: Simulation, Implementation, Brute force, Array
Solved: No attempts yet

Problem

Shark Elementary School has one classroom, which can be represented as an N×N grid. The number of students attending the school is N2. Today is the day to assign every student a seat. Students are numbered from 1 to N2, and (r, c) denotes row r, column c. The top-left cell of the classroom is (1, 1), and the bottom-right cell is (N, N).

The teacher has decided the order of the students and has surveyed the 4 students each student likes. Now the teacher wants to assign seats in that order using the following rules. Each cell holds at most one student, and two cells (r1, c1) and (r2, c2) are adjacent if |r1 - r2| + |c1 - c2| = 1.

Among the empty cells, choose the cell with the most adjacent cells occupied by students the student likes.
If several cells satisfy rule 1, choose the cell with the most adjacent empty cells.
If several cells also satisfy rule 2, choose the cell with the smallest row number; if there are still several, choose the cell with the smallest column number.

For example, consider the case where N = 3 and the order of the N2 students and the students each likes are as follows.

Student number	Numbers of liked students
4	2, 5, 1, 7
3	1, 9, 4, 5
9	8, 1, 2, 3
8	1, 9, 3, 4
7	2, 3, 4, 8
1	9, 2, 5, 7
6	5, 2, 3, 4
5	1, 9, 2, 8
2	9, 3, 1, 4

First, student 4's seat must be assigned. Every cell in the classroom is currently empty. By rule 2, cell (2, 2), which has the most adjacent empty cells, becomes student 4's seat.



	4

Next is student 3. The cells satisfying rule 1 are (1, 2), (2, 1), (2, 3), (3, 2). All of them have 2 adjacent empty cells. Therefore, by rule 3, (1, 2) becomes student 3's seat.


	3
	4

Next is student 9. The students student 9 likes are 8, 1, 2, 3, and among them 3 is seated. The cells with the most adjacent liked students are (1, 1) and (1, 3). Both have 1 adjacent empty cell and row number 1. Therefore, by rule 3, (1, 1) becomes student 9's seat.


9	3
	4

The next student to be seated is student 8. Since (2, 1) has the most adjacent liked students, this becomes the seat.


9	3
8	4

Let us assign student 7's seat. The cells satisfying rule 1 are (1, 3), (2, 3), (3, 1), (3, 2), 4 in total, and the cells with the most adjacent empty cells are (2, 3) and (3, 2). The smaller row number makes (2, 3) student 7's seat.


9	3
8	4	7

Assigning every student's seat this way gives the following.


9	3	2
8	4	7
5	6	1

Now the students' satisfaction must be computed. Satisfaction can be computed after all seats are assigned. To compute a student's satisfaction, count the liked students seated in adjacent cells. If that value is 0 the satisfaction is 0, if 1 it is 1, if 2 it is 10, if 3 it is 100, and if 4 it is 1000.

Find the total sum of the students' satisfaction.

Input

The first line gives N. From the second line, N2 lines follow, each containing one student's number and the numbers of the 4 students that student likes, in the order the teacher assigns seats.

Student numbers are distinct, and the 4 students any student likes are all different. The student numbers and liked student numbers in the input are natural numbers less than or equal to N2. No student likes themselves.

Output

Print the total sum of the students' satisfaction on the first line.

Constraints

3 ≤ N ≤ 20

Examples2

Example 1

Input

Expected output

Example 2

Input

Expected output