칸

엘리는 최근 불가리아 칸에 대해 배웠다. 칸은 유목 부족의 지도자로, 수백 년 동안 대륙을 떠돌다가 마침내 지금의 불가리아 자리에 정착했다.

칸이 살던 대륙은 N * M개의 지역으로 나뉘어 있었고, 이들은 N개의 행과 M개의 열로 이루어진 직사각형으로 편리하게 배치되어 있었다. 칸은 특정 지역에서 1년을 보내며 부족과 함께 그곳의 모든 식량을 먹어치웠다. 그 해가 끝나면 변을 맞대고 있는 (최대) 네 이웃 지역 중 하나로 이동하여 다음 1년을 보내며 그곳의 모든 식량을 먹어치우는 식이었다. 이웃 지역으로의 이동은 그 해가 끝나는 순간 즉시 일어나는 것으로 본다(1년 전체에 비하면 며칠의 이동이 무슨 대수인가?). 칸은 같은 지역에서 두 해 연속 머무르지 않는다. 그러면 부족이 굶어 죽기 때문이다.

각 지역은 부양할 수 있는 최대 식량량이 정해져 있었다. 이 최대량을 지역별로 정수 Aij로 나타내자. 칸이 한 지역의 식량을 모두 먹고 그곳을 떠나면, 그곳의 식량은 다시 채워지기 시작했다. 칸이 떠난 다음 해에는 식량 1단위가 생산되었다. 그다음 해에는 양이 두 배가 되고, 그다음 해에는 다시 두 배가 되는 식으로, 그 지역의 최대량 Aij에 도달할 때까지 늘어났다. 식량량은 지역이 부양할 수 있는 최대량을 절대 넘지 않는다. 예를 들어 어떤 지역의 최대 식량량이 Aij = 55라면, 칸이 떠난 뒤 10년 동안 각 해가 시작될 때의 식량량은 각각 0, 1, 2, 4, 8, 16, 32, 55, 55, 55단위이다.

칸은 어떤 지역이 최대 식량량까지 회복되기 전에는 그곳으로 돌아가면 안 된다는 것을 알고 있었다. 그렇지 않으면 그 지역을 영구적으로 손상시킬 수 있었고, 칸은 그러기를 원하지 않았다. 그래서 때로는 식량이 더 적은 지역(예: 42단위)을 식량이 더 많은 지역(예: 64단위지만 최대량이 71단위인 지역)보다 선택하기도 했다. 앞 문단의 예에서 칸은 그 지역을 떠난 지 8년째가 시작될 때 돌아갈 수 있다. 그때가 최대 식량량에 도달한 첫 해이기 때문이다.

엘리는 대륙에 대한 정보를 N개의 행과 M개의 열을 가진 행렬 A로 가지고 있다. A는 각 지역의 최대 식량량을 나타낸다. 처음에는 모든 지역이 최대 식량량을 가지고 있었다. 칸이 첫해를 왼쪽 위 지역에서 보냈다는 것을 알 때, K년 동안 칸이 먹을 수 있는 최대 식량량은 얼마인가?

표준 입력의 첫 줄에는 세 정수 N, M, K가 주어진다. 각각 행의 수, 열의 수, 연도의 수이다. 다음 N개 줄에는 M개의 정수 Aij가 주어지며, 각 지역의 최대 식량량을 나타낸다.

표준 출력의 한 줄에 정수 하나를 출력한다. 칸이 최적으로 이동했을 때 먹을 수 있는 최대 총 식량량이다.

• 1 ≤ N, M ≤ 10
• 1 ≤ K ≤ 100
• 10 ≤ Aij ≤ 100
• 식량이 완전히 회복되지 않은 지역에 들어가지 않는다는 규칙을 위반하지 않는 경로가 항상 존재함이 보장된다.

첫 번째 예에서 칸이 최대 식량량(254단위)을 먹기 위해 방문할 수 있는 지역은 각각 11, 17, 13, 96, 15, 17, 22, 14, 16, 18, 15단위의 식량을 가진 지역들일 수 있다. 이 경로에서 칸은 한 지역만 두 번 방문하며, 그 지역은 마지막 15단위 식량 지역이다. 또한 마지막 해가 지난 뒤에는 이웃한 어떤 지역도 식량이 아직 회복되지 않았으므로 칸은 이동할 수 없다. 이 해가 마지막 해이므로 괜찮지만, 칸이 1년 더 이동해야 했다면(즉, K가 11이 아니라 12였다면) 같은 지역에 머무르는 것은 선택지가 아니므로 다른 경로를 택했을 것이다. K = 12일 때 가능한 경로는 11, 17, 13, 96, 15, 18, 16, 17, 22, 14, 10, 24이고 합은 273이다.