Bajt's father has fried a lot of pancakes. He arranged them into $n$ stacks of $m$ pancakes each. The pancakes in each stack are arranged from largest to smallest (i.e., the largest pancake is at the bottom of the stack). He allowed Bajt to eat $k$ of these pancakes. To avoid a mess in the kitchen, Bajt can only eat pancakes from the top of a stack (he cannot take the largest pancakes from the bottom, as his father is afraid this would result in pancakes scattered all over the kitchen).

Bajt quickly realized that these rules are not in his favor—after all, the largest pancakes are at the bottoms of the stacks—and he quickly turned some of the stacks upside down. He wanted to turn them all over, but he didn't have time, and now his father is vigilantly watching his every move. Bajt must therefore plan how to eat as many pancakes as possible.

Input

The first line of input contains three integers $n$, $m$, and $k$ ($n, m \ge 1$; $n \cdot m \le 300\,000$; $1 \le k \le n \cdot m$), representing the number of pancake stacks, the number of pancakes in each stack, and the number of pancakes Bajt is allowed to eat, respectively.

The next $n$ lines contain descriptions of the stacks; the $i$-th of these lines contains a sequence of $m$ integers $a_{i,1}, \dots, a_{i,m}$ ($1 \le a_{i,j} \le 10^{12}$). The number $a_{i,j}$ represents the size of the $j$-th pancake from the top in the $i$-th stack. For each $i$, either $a_{i,j} \ge a_{i,j+1}$ for all $j$, or $a_{i,j} \le a_{i,j+1}$ for all $j$.

Output

Output a single integer – the maximum total size of $k$ pancakes that Bajt can eat.

Examples

Input 1

3 3 5
1 2 3
1 2 3
3 2 1

Output 1

11

Input 2

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

Output 2

4999999999999

Note

In the first example, to eat pancakes with a total size of 11, Bajt can, for example, eat all three pancakes from the first stack (with sizes 1, 2, and 3, respectively) and the two top pancakes from the last stack (with sizes 3 and 2, respectively). It can be proven that Bajt cannot eat pancakes with a total size greater than 11.

In the second example, Bajt can eat all pancakes except one. It is optimal for him to leave the bottom pancake of the second stack uneaten.