Problem Description

Bajtek’s dad made many pancakes. He stacked them into $n$ stacks, with $m$ pancakes in each stack. In every stack, the pancakes are arranged from largest to smallest (that is, the largest pancake is at the bottom of the stack). He allows Bajtek to eat $k$ pancakes.

To avoid making a mess in the kitchen, Bajtek can only eat pancakes from the top of a stack (he cannot take the largest pancake from the bottom, because his dad worries that this would cause the pancakes to scatter all over the kitchen).

Bajtek quickly realized that these rules are not good for him—after all, the largest pancakes are at the bottom—so he immediately flipped some of the stacks over. He wanted to flip all of them, but he did not have enough time, and now his dad is watching his every move. Therefore, Bajtek must plan how to eat pancakes so that the total size is as large as possible.

Input Format

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

The next $n$ lines describe the stacks. The $i$-th line contains $m$ integers $a_{i,1}, \dots, a_{i,m}$ ($1 \le a_{i,j} \le 10^{12}$). The number $a_{i,j}$ is 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 Format

Output one integer: the maximum possible total size of the $k$ pancakes that Bajtek can eat.

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

11

2 3 5
999999999999 1000000000000 1000000000000
1000000000000 1000000000000 999999999999

4999999999999

Hint

Explanation of the examples: In the first example, to get a total size of $11$, Bajtek can eat all three pancakes from the first stack (with sizes $1$, $2$, and $3$ in this order), and the top two pancakes from the last stack (with sizes $3$ and $2$ in this order). It can be proven that Bajtek cannot eat pancakes with a total size greater than $11$.

In the second example, Bajtek can eat all pancakes except one. He should leave the bottom pancake of the second stack uneaten.

Translated by ChatGPT 5