행렬 게임

문제

훈과 찬은 행렬 게임을 하고 있다. 두 사람은 각각 $N\times N$ 행렬 $A=(a_{ij})$와 $B=(b_{ij})$를 가지고 있다. 게임은 $M$개 라운드로 구성되고, 각 라운드에서 훈과 찬은 동시에 각각 숫자 $\alpha$와 $\beta$를 부른다. 여기서, $\alpha$와 $\beta$는 $1$과 $N$사이의 정수이다. 그러면 훈과 찬은 각각 $a_{\alpha \beta }$와 $b_{\alpha \beta }$의 점수를 얻는다.

전날 밤 꿈에서, 훈은 찬이 게임의 각 라운드에서 부를 $M$개 숫자 ${\beta }_1,{\beta }_2,\dots ,{\beta }_M$를 보았다. 따라서 훈은 Diff 가 최대가 되는 $M$개 숫자 ${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_M$을 선택할 수 있다. 여기서, Diff 는 ${\sum }_{k=1}^M|a_{{\alpha }_k{\beta }_k}-b_{{\alpha }_k{\beta }_k}|$로 정의하고, 이것은 둘의 각 라운드 점수의 절대값 차이의 총 합이다.

각 라운드에서 찬이 부르는 $M$개 숫자가 주어지면, 훈이 Diff 를 최대화하는 $M$개 숫자들을 선택할때, Diff 의 최대값을 출력하는 프로그램을 작성하시오.

입력

입력은 표준 입력을 사용한다. 첫 번째 줄에 두 정수 $N$과 $M$ ($1\le N\le 1000$, $1\le M\le 1000000$)이주어진다. 여기서, $N$은 훈과 찬이 게임에서 가지고 있는 행렬의 크기이고 $M$은 게임의 라운드개수이다. 다음 이어지는 $N$개 줄의 $i$번째 줄에는 훈의 행렬의 $i$번째 행의 값들을 나타내는 $N$개 정수가 주어진다. 다음 이어지는 $N$개 줄의 $i$번째 줄에는 찬의 행렬의 $i$번째 행의 값들을 나타내는 $N$개 정수가 주어진다. 이 행렬들의 값은 $0$ 과 $1000$ 사이의 정수이다. 다음 줄에는 찬이 각 라운드에서 부르는 $1$ 과 $N$ 사이의 $M$개 정수가 주어진다.

출력

출력은 표준 출력을 사용한다. 훈이 Diff 를 최대화하는 $M$개 숫자를 선택할 때, Diff 의 최대값을 출력한다.

예제 입력 1 복사

2 2
1 2
0 1
3 1
2 1
2 1

예제 입력 2 복사

2 3
5 0
2 6
3 3
3 2
1 1 2

예제 출력 1 복사

3

예제 출력 2 복사

8