33561번 - 임스의 땅따먹기

문제

임스는 $N \times N$ 크기의 격자판 모양의 국가에서 살고 있다. 격자판의 $i$행 $j$열에 위치한 칸에는 해당 칸의 가치를 나타내는 음이 아닌 정수 $w_{ij}$가 적혀 있다.

임스는 가지고 있는 땅의 일부분을 자신의 영역으로 정복하려고 한다. 임스가 정복하려고 하는 영역은 다음 조건을 만족해야 한다.

• 임스의 영역은 각 변이 격자판과 평행한 정사각형 영역이다. 구체적으로 영역은 1ドル \leq a \leq b \leq N, 1 \leq c \leq d \leq N, b - a = d - c$를 만족하는 정수 $(a, b, c, d)$에 대하여 다음과 같이 정의한다.
  • $a \leq x \leq b, c \leq y \leq d$를 만족하는 정수 $x, y$에 대해 $x$행 $y$열에 위치한 칸은 영역에 포함되어야 한다.
  • $a \leq x \leq b, c \leq y \leq d$를 만족하지 않는 1ドル \leq x, y \leq N$에 대해 $x$행 $y$열에 위치한 칸은 영역에 포함되지 않아야 한다.
• 임스는 가치가 없는 땅을 싫어하기 때문에 영역 내부에는 가치가 0ドル$인 칸은 없어야 한다. 즉, $(a, b, c, d)$로 정의된 영역에 대하여 $a \leq x \leq b,ドル $c \leq y \leq d$를 만족하는 모든 정수 $x, y$에 대해 $w_{xy} \neq 0$을 만족해야 한다.
• 영역의 가치는 영역 내부 칸의 가치의 합으로 정의된다. 즉, $(a, b, c, d)$로 정의된 영역의 가치는 $\displaystyle \sum_{a \leq x \leq b \land c \leq y \leq d} w_{xy}$이다.

하지만 임스는 가치가 없는 칸이 너무 많다는 것을 알게 되었다. 그래서 가치가 없는 칸에 건물을 건설해 가치를 올리고자 한다. 임스는 총 $K$개의 설계도를 가지고 있으며, 임스는 이 중 최대 $K$개를 사용하여 가치가 없는 칸에 건물을 건설할 수 있다.

• 임스는 가지고 있는 $K$개의 설계도 중 $i$번째 설계도는 $d_{i}$의 가치를 가지고 있다.
• $d_{i}$의 가치를 가지고 있는 설계도를 사용하면 해당 칸에 가치가 $d_{i}$인 건물을 건설할 수 있으며, 이로 인해 해당 칸의 가치가 $d_{i}$ 증가한다.
• 임스는 현재 가치가 없는 칸마다 설계도를 최대 한 번 사용하여 가치를 올릴 계획이다.
• 한 번 사용한 설계도는 다시 사용할 수 없다.

임스는 자신이 가지고 있는 설계도를 적절히 사용한 후, 영역 중 가치가 최대인 영역을 자신의 영역으로 정복하려고 한다. 하지만 가치가 최대인 영역이 어디인지 계산하지 못하고 있다. 임스를 도와주자!

입력

첫 번째 줄에 임스가 가지고 있는 땅의 크기를 나타내는 정수 $N$이 주어진다. $(1 \leq N \leq 500)$

다음 $N$개의 줄에 걸쳐 $i$번째 줄에 $N$개의 음이 아닌 정수 $w_{ij}$가 공백으로 구분되어 주어진다. $(0 \leq w_{ij} \leq 9)$

$N + 2$번째 줄에 임스가 가지고 있는 설계도의 개수 $K$가 주어진다. $(1 \leq K \leq 100 ,円 000)$

$N + 3$번째 줄에 임스가 가지고 있는 설계도의 가치 $d_{1}, d_{2}, \cdots, d_{K}$가 공백으로 구분되어 주어진다. $(1 \leq d_{i} \leq 9)$

출력

첫 번째 줄에 임스가 가진 설계도를 적절히 사용한 후 가치가 최대인 영역의 가치를 구해 출력한다.

제한

힌트