Number Trapezium

Time Limit: 1000 mSec

Memory Limit: 32768 KB

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

Hint

Source


提交代码