Descrpition

有 $n$ 个长度为 $m$ 的队列

定义一次操作为将某一个非空的队列队首元素出队，并将它的权值加入到答案中

求在执行恰好 $k$ 次操作后出队元素的权值之和的最大值

Input

第一行三个正整数 $n,m,k$ ，分别表示队列的个数，队列的长度及操作次数

接下来 $n$ 行，每行 $m$ 个数，第 $i$ 行的第 $j$ 个数 $a_{i,j}$ 表示第 $i$ 个队列的第 $j$ 个元素的权值

Output

一行一个正整数，表示最大的权值

Sample

3 4 7
1 -1 3 4
2 -1 -2 -3
0 -2 2 3

8

Limitation

对于 $20 \%$ 的测试数据， $n = 1,m \leq 30$

对于 $50 \%$ 的测试数据， $n \leq 5,m \leq 30$

对于 $100 \%$ 的测试数据， $n,m \leq 100,k \leq n \times m,-10^9 \leq a_{i,j} \leq 10^9$