Data Flow (APCS 2021-01 Intermediate)

There are \(n\) servers numbered from \(0\) to \(n-1\) and \(m\) cities numbered from \(0\) to \(m-1\).

Every server must send data to every city. The value \(Q[i][j]\) is the amount of data flow that server \(i\) must send to city \(j\).

The engineers propose \(k\) server placement plans. A plan contains

where \(c_i\) is the city containing server \(i\). The city containing a server is the source of its transmissions, while the city receiving the data is the destination.

To calculate the cost of one plan, first combine all flows having both the same source city and the same destination city. Thus, the total flow from city \(u\) to city \(v\) is

Flows with different source cities must not be combined. After obtaining \(F[u][v]\), calculate the cost of this combined flow as follows:

• If \(u=v\), each unit costs \(1\), so the cost is \(F[u][v]\).
• If \(u\ne v\) and \(F[u][v]\le1000\), each unit costs \(3\).
• If \(u\ne v\) and \(F[u][v]>1000\), the first \(1000\) units still cost \(3\) each. Only the part above \(1000\) costs \(2\) per unit. The cost is

The total cost of a plan is the sum over every ordered pair of cities \((u,v)\). Find the minimum total cost among all \(k\) plans.

Input

The first line contains three integers \(n,m,k\).

The next \(n\) lines each contain \(m\) integers. The \(j\)-th integer on the \(i\)-th line is \(Q[i][j]\).

Each of the next \(k\) lines contains \(n\) integers \(c_0,c_1,\ldots,c_{n-1}\) describing one placement plan.

Constraints

• \(1\le n,m,k\le50\)
• \(0\le Q[i][j]\le1000\)
• \(0\le c_i<m\)
• All input values are integers.

Output

Output one integer: the minimum total cost among all plans.

Scoring

The two sample cases are judged but worth zero points. There are exactly \(20\) scored test groups, each worth \(5\) points:

• Groups \(1\)–\(4\) (\(20\) points): \(n=1\) and \(k=1\).
• Groups \(5\)–\(10\) (\(30\) points): \(n=1\).
• Groups \(11\)–\(20\) (\(50\) points): no additional constraints.

Sample Input 1

2 3 3
30 23 23
5 25 3
0 0
0 1
0 2

Sample Output 1

217

Sample Explanation 1

The total costs of the three plans are \(257\), \(217\), and \(261\), respectively, so the answer is \(217\).

For the second plan \((0,1)\), server \(0\) is in city \(0\) and server \(1\) is in city \(1\). The costs of the six transmissions add up to

Sample Input 2

3 4 5
500 400 800 200
500 400 100 600
450 420 800 790
0 0 0
0 1 2
0 2 2
2 1 2
1 1 1

Sample Output 2

13470

Source

APCS January 2021, Implementation Problem 2. The rules are based on ZeroJudge f606, Data Flow and Yi-Zhe Wang's solution notes. The statement was rewritten for AACPOJ.