Matrix Game

Interview

Time limit1sMemory limit2048 MB

Summary

For each column, pick the row that maximizes |a - b| there, then sum those maxima over all M columns Chan calls to get the largest possible Diff.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

Hun and Chan are playing a matrix game. Each has an $N \times N$ matrix, $A = (a_{ij})$ and $B = (b_{ij})$ .

The game has $M$ rounds. In each round, Hun and Chan call out the numbers $\alpha$ and $\beta$ at the same time. Here $\alpha$ and $\beta$ are integers between 1 and $N$ . Hun scores $a_{\alpha\beta}$ points and Chan scores $b_{\alpha\beta}$ points.

Last night Hun dreamed the $M$ numbers $\beta_1, \beta_2, \dots, \beta_M$ that Chan will call in the rounds. Hun can therefore choose $M$ numbers $\alpha_1, \alpha_2, \dots, \alpha_M$ that maximize Diff. Diff is defined as $\sum_{k=1}^M \left| a_{\alpha_k \beta_k} - b_{\alpha_k \beta_k} \right|$ , the sum over all rounds of the absolute difference between the two players' scores in that round.

Given the $M$ numbers Chan calls in each round, write a program that outputs the maximum possible value of Diff when Hun chooses his $M$ numbers to maximize it.

Input

The first line contains two integers $N$ and $M$ ( $1 \le N \le 1,000$ , $1 \le M \le 1,000,000$ ). $N$ is the size of each player's matrix, and $M$ is the number of rounds.

The next $N$ lines contain Hun's matrix $A$ , where line $i$ holds the $N$ values of row $i$ . The following $N$ lines contain Chan's matrix $B$ in the same way. All matrix values are integers between 0 and 1,000.

The last line contains $M$ integers between 1 and $N$ , the numbers Chan calls in each round.

Output

Print the maximum value of Diff when Hun chooses his $M$ numbers to maximize it.

Examples2

Example 1
Input
```
2 2
1 2
0 1
3 1
2 1
2 1
```
Expected output
```
3
```
Example 2
Input
```
2 3
5 0
2 6
3 3
3 2
1 1 2
```
Expected output
```
8
```