Center Supermeowket is the biggest chain of supermarkets on the cat planet. There is currently a sale going on in this supermarket that applies as follows:

There are ~n~ prize packages; each package contains ~m~ prizes. The ~j~ prize of the ~i~-th package has a value ~A_{i, j}~. The prizes in a single package are also arranged in non-decreasing order (any prize is at least as valuable as the prize that precedes it).

A customer can redeem prize packages using loyal customer points. More precisely, for each prize package, the customer can use ~x~ points (for ~0 \le x \le m~) to redeem the first ~x~ prizes of a package. Note that a package can only be redeemed once.

Neko, a long-engaged customer of Center Supermeowket, currently has ~k~ loyal customer points for redeeming. He wants to know if done optimally, what is the maximum sum of prize values he can redeem.

Input

The first line contains three integers ~n~, ~m~, ~k~ (~1 \le n \le 10^5~, ~1 \le m \le 10~, ~1 \le k \le n \cdot m~) — the number of prize packages, the number of prize per package, and Neko's current loyal customer points, respectively.

The ~i~-th line of the following ~n~ lines contains ~m~ positive integers ~A_{i,1}, A_{i,2}, \ldots, A_{i,m}~ (~1 \le A_{i,1} \le A_{i,2} \le \ldots \le A_{i,m} \le 10^9~) — denoting the prize values of the ~i~-th package.

Output

Output a single integer: the maximum possible sum of prize values.

Scoring

• Subtask 1 (~30~ points): ~n \le 15~ and ~m = 2~

• Subtask 2 (~45~ points): ~n \le 300~

• Subtask 3 (~75~ points): No additional constraints

The total score for this problem is ~150~.

Sample Input 1

3 2 3
1 3
2 9
7 8

Sample Output 1

18

Notes

Neko will redeem for 2 prizes from the second package, and 1 prize from the third package. The sum of values of the prizes is ~2 + 9 + 7 = 18~.