32207번 - 꿀잼 루비 문제

문제

보물 사냥꾼 나도리는 $N \times M$ 격자 모양의 루비 광산에 도착했다. 격자의 $i$행 $j$열의 칸에는 가치 $A_{ij}$의 루비가 묻혀 있고, 나도리는 이 중 최대 $K$개의 루비를 캐려고 한다.

하지만 나도리의 숙적 너도리가 등장하여 광산에 어떠한 장치를 설치하였다. 이 장치는 만약 나도리가 상하좌우로 인접한 두 칸 모두에서 루비를 캔다면 그 즉시 광산을 폭발시키고 말 것이다.

나도리가 장치를 작동시키지 않으면서 루비 가치의 합이 최대가 되도록 캐는 방법을 찾아보자.

입력

첫째 줄에 정수 $N,ドル $M,ドル $K$가 공백을 사이에 두고 주어진다. $(1 \le N, M \le 1,000円$; 1ドル \le K \le 5)$

둘째 줄부터 $N$개의 줄에 걸쳐 루비의 가치가 $M$개의 정수로 공백을 사이에 두고 주어진다. 1ドル \le i \le N$ 과 1ドル \le j \le M$에 대해, $i + 1$번째 줄의 $j$번째 정수는 $A_{ij}$를 나타낸다. $(0 \le A_{ij} \le 1,000円)$

출력

나도리가 캘 수 있는 루비 가치의 합의 최댓값을 출력한다.

제한

힌트