Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 1065 Accepted: 223

Description

When seeing his Citizens, Panagola always waves his hands. He may get tired and need a break. So please never make Panagola travel in a same west-east road for more than k minutes. If it takes p minutes to pass a love-hate zone, we say the length of that love-hate zone is p. Of course you know every love-hate zone's length.

The figure below illustrates the case in sample input. In this figure, a best route is marked by thicker lines.

Input

There are multiple test cases. Input ends with a line containing three zeros.
Each test case consists of 2 * n + 3 lines.
The first line contains three integers: n, m and k.(0<n<=100,0<m<=10000, 0<=k<=3000000)
The next n+1 lines stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the welcome values of the road's m love-hate zones, in west to east order.
The last n+1 lines also stands for n + 1 west-east roads in north to south order. Each line contains m integers showing the lengths (in minutes) of the road's m love-hate zones, in west to east order.

Output

For each test case, output the sum of welcome values of the best route. The answer can be fit in a 32 bits integer.

Sample Input

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

Sample Output

27

Source

[Submit]   [Go Back]   [Status]   [Discuss]