提示: 欢迎访问OurACM平台。
Problem 1020 Number Trapezium

Accept: 70    Submit: 273
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

 1 2

  5 0 2

1 10 0 6

The above figure shows a number trapezia. Write a program that calculates the highest sum of numbers passed on k distinct routes that starts at the top line and ends on the base. Each route step can go either diagonally down to the left or diagonally down to the right. Each route should not share the same path, but a node can be reached for more than one route.

Input

There are multiple test cases. The first line of each test case contains three integers: n,m,k(1<=k<=m<=30,1<=n<=30). n indicates the number of rows in the trapezia, m indicates the number of numbers in the top row, and k stands for the number of routes desired. The following n lines describe the data of the trapezia.

Output

Print the highest sum for each case, one per line.

Sample Input

3 2 2 1 2 5 0 2 1 10 0 6

Sample Output

26

Submit  Back  Status  Discuss