시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB68302746.552%

문제

집순이 아리는 오랜만에 집 밖을 나와 쿠기를 만나러 학교를 가려고 한다. 이때 아리는 겸사겸사 학교로 가는 경로에 있는 장소들에서 최대한 많은 일을 처리하고 가려고 한다.

아리는 N × M 의 격자 공간에서 움직이고, 집은 격자 공간의 최좌측 상단 (0, 0), 학교는 최우측 하단(N-1, M-1)이다. 아리의 현재 위치가 (a, b)일 때, 항상 (a+1, b), (a, b+1), (a+1, b+1) 위치 중 하나로 움직인다. 단, 한 번 이동할 때마다 추가로 1분이 걸린다.

각 위치에서 할 수 있는 일들과 그 일들을 모두 수행했을 때 걸리는 시간이 주어진다. 각 장소들에서 아리는 일을 처리할지 말지 선택할 수 있으며, 한 장소에서 일을 시작하면 모든 일을 완료할 때까지 중단할 수 없고 일들을 수행하면 걸리는 시간만큼 시간이 소요된다.

명랑한 아리가 쿠기와의 약속을 위해 집에서 학교로 갈 때, 집에서 학교로 가는 경로의 장소들에서 약속까지 남은 시간 동안 가장 많이 할 수 있는 일의 양을 구하자.

입력

정수 NM이 주어지고(2 ≤ N, M ≤ 50), 아리에게 남은 시간 정수 T가 분 단위로 주어진다. (N + M - 1 ≤ T ≤ 500)

먼저 i(0 ≤ i < N)번째 행 j(0 ≤ j < M)번째 열의 장소에서 할 수 있는 일들의 개수, 정수 wij(0 ≤ wij ≤ 100)가 NM열에 걸쳐서 주어지고,

다음으로 i(0 ≤ i < N)번째 행 j(0 ≤ j < M)번째 열의 장소에서 일들을 모두 수행했을 때 걸리는 시간, 정수 tij(0 ≤ tij ≤ 100)가 NM열에 걸쳐서 주어진다.

단, 집과 학교에서 아리가 할 수 있는 일은 없다.

출력

쿠기와 학교에서 만나기로 한 약속을 지키면서, 약속까지 남은 시간 내 아리가 가장 많이 할 수 있는 일의 수를 출력한다.

예제 입력 1

6 5 15
0 2 1 3 1
3 1 4 2 2
1 4 1 3 1
2 1 4 1 7
1 3 2 3 1
4 1 1 5 0
0 1 3 2 5
4 3 5 2 3
1 2 2 2 1
3 1 2 1 2
1 3 1 2 1
3 2 1 1 0

예제 출력 1

18

N = 6, M = 5, T = 15

0,0 2,1 1,3 3,2 1,5
3,4 1,3 4,5 2,2 2,3
1,1 4,2 1,2 3,2 1,1
2,3 1,1 4,2 1,1 7,2
1,1 3,3 2,1 3,2 1,1
4,3 1,2 1,1 5,1 0,0

아리는 6행 5열 격자 공간에서 움직이는 데, 남은 시간은 15분이다.

집(0, 0)에서 (2, 1)까지 두 번 이동하여 2분이 소요 → (2, 1) 장소에서 2분을 소요하면서 일 4개를 처리 → 다음으로 (3, 2)로 이동할 때 1분 소요 → (3, 2)에서 2분을 소요하면서 일 4개를 처리 → (4, 2)로 이동할 때 1분 소요 → (4, 2)에서 1분을 소요하면서 일 2개를 처리 → (4, 3)로 이동할 때 1분 소요 → (4, 3)열에서 2분을 소요하면서 일 3개를 처리 → (5, 3)로 이동할 때 1분 소요 → (5, 3)에서 1분을 소요하면서 일 5개를 처리 → 학교(5, 4)로 이동하면서 1분을 소요하고 종료한다.

예제 입력 2

3 3 5
0 10 0
13 20 11
45 14 0
0 10 10
10 10 10
10 10 0

예제 출력 2

0

N = 3, M = 3, T = 5

0,0 10,10 0,10
13,10 20,10 11,10
45,10 14,10 0,0

아리는 3행 3열 격자 공간에서 움직이는 데, 남은 시간은 5분이다.

집(0, 0)에서 학교(2, 2)까지 경로에서 일을 하나라도 하는 순간 아리는 약속을 어기게 되기 때문에 어떤 일도 하지 못한다.