꿀잼 루비 문제

보물 사냥꾼 나도리는 $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$개의 정수가 공백으로 구분되어 주어진다. $i+1$번째 줄의 $j$번째 정수가 $A_{ij}$이다. ($1 \le i \le N$, $1 \le j \le M$, $0 \le A_{ij} \le 1\,000$)

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