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~.

## Comments