Electronic components in a latin square

An empty matrix on a computer card is to be fitted with components. The matrix is made of N×N square cells in rectangular grid and each cell of the matrix will contain exactly one component. There are N types of components and N components of each type. The components of the same type are considered identical. The layout of the components in the matrix is regulated by additional rules: First, in any row and in any column of the matrix there shoud be exactly one component of each type. Second, some types of components cannot occupy adjacent cells in the matrix. Two cells are adjacent if they share common border horizontally or vertically.

There is a list of forbidden pairs of adjacent types. Each pair in the lists specifies two different types of components. Any pair of types of any two adjacent components in the final matrix layout must not be present in this list. A layout of the components in the matrix which satisfies all prescribed rules mentioned here is called a feasible configuration. We note that sometimes it is possible to construct more than one feasible configuration of given components.

For each particular component type T and for each position P in the matrix there is a given price of installing a component of type T at the position P.

     


Image 1. Example of matrix of size 5×5 and five component types marked by different colors. The upper row of the image shows price tables for each component type and for each position in the matrix. The lower row of the image shows the feasible configuration which price is minimum possible provided that the list of forbidden pairs of adjacent types contains one pair (2, 5), that is, a blue and a yellow component must never occupy adjacent positions. The positions of particular component types in the final matrix is also highlighted in their corresponding price tables.

The task

Find a feasible configuration with the minimum price. The price of the configuration is equal to the sum of prices of installing all N×N components in the matrix.


Input

First input line contains single value N representing the size of the matrix, number of component types and number of components of each type. We suppose that the types are labeled 1, 2, ..., N.
Next, there are N tables. Each table consists of N rows and N columns. The value at the position [i][j] in the k-th table (k = 1, 2, ..., N) represents the price of mounting a component of type k in the cell at position [i][j] in the matrix. Each line contains one table row, the values in the row are separated by spaces. Each table is followed by one empty line.
The last part of the input is the list of forbidden pairs of adjacent types. The list begins with a line which contains single value K representing the length of the list. Then, K lines follow. Each line contains one pair of forbidden adjacent types, the values on a line are separated by space. The list may be empty, in such case K is 0.
All prices are non-negative integers not larger than 1000. The value of N does not exceed 10.

Output

Output contains single text line with one integer representing minimum possible price of a feasible configuration. It is guaranteed that at least one feasible configuration exists in all problem instances presented here.

Example 1

Input
5
0  1  1  0  4                     
1  0  1  0  1                      
4  0  0  4  0                     
1  4  1  4  1                     
1  4  4  1  1                      

1  1  1  4  0
1  1  4  0  1
1  4  0  1  1 
4  0  1  1  1
0  1  1  1  1

0  0  4  4  4
0  0  4  4  4
0  0  4  4  4 
4  4  0  0  0 
4  4  0  0  0

1  1  1  1  1 
1  1  1  1  1 
1  1  1  1  1
4  4  4  0  0
4  4  4  0  0

0  1  4  0  1
4  0  1  4  0  
1  4  0  1  4 
0  1  4  0  1 
4  0  1  4  0 

1
2 5
Output
18
The data and the solution of Example 1 are depicted in Image 1. Additionally and for reader's reference, we state that the value of the solution would be 13 if the list of forbidden pairs of adjacent types was empty in this example.

Example 2

Input
4
1   1 10 10
10  1  1 10
10 10  1  1
 1 10 10  1

10  1  1 10
10 10  1  1
 1 10 10  1
 1  1 10 10

10 10  1  1
 1 10 10  1
 1  1 10 10
10  1  1 10

 1 10 10  1
 1  1 10 10
10  1  1 10
10 10  1  1

2
1 3
2 4
Output
16
The solution is the configuration depicted schematically bellow. In each cell the component type and its price are listed.
[1  1] [2  1] [3  1] [4  1] 
[4  1] [1  1] [2  1] [3  1] 
[3  1] [4  1] [1  1] [2  1] 
[2  1] [3  1] [4  1] [1  1] 

Example 3

Input
4
1   1 10 10
10  1  1 10
10 10  1  1
 1 10 10  1

10  1  1 10
10 10  1  1
 1 10 10  1
 1  1 10 10

10 10  1  1
 1 10 10  1
 1  1 10 10
10  1  1 10

 1 10 10  1
 1  1 10 10
10  1  1 10
10 10  1  1

1
1 4
Output
52
The solution is the configuration depicted schematically bellow. In each cell the component type and its price are listed. Note that the difference between Example 2 and Example 3 is only in the list of forbidden pairs of adjacent types.
[1  1] [2  1] [4 10] [3  1] 
[3  1] [1  1] [2  1] [4 10] 
[4 10] [3  1] [1  1] [2  1] 
[2  1] [4 10] [3  1] [1  1] 

Note

The scheme of filling a square matrix of size N×N with N different types of items and each item taken N times and with the condition that each row and column contain exactly one item of each type is know as a latin square. (We generally do not consider any list of forbidden pairs of types in latin square.) The numbers of different latin squares of different sizes is listed in the table bellow. Two latin squares are different if they differ in at least one position (cell).

Latins squares of size N x N

 N  Number |   N                                  Number   
-----------+---------------------------------------------
 1       1 |   6                               812851200        
 2       2 |   7                          61479419904000
 3      12 |   8                   108776032459082956800
 4     576 |   9            5524751496156892842531225600
 5  161280 |  10   9982437658213039871725064756920320000

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set