25170번 - 명랑한 아리의 외출

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

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

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

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

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

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

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

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

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