C. Salameh Leveling
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a grid of $$$(n * m)$$$ points , each point contains a hidden box. When you collect it, you either gain some experience points "XPs" , or you lose some for being a horrible greedy player.

The grid has a guardian who won't let you take more than $$$k$$$ boxes. Moreover, each $$$n$$$ points forming a column has its own guardian. This guardian won't let you open more than $$$i$$$ boxes in the column numbered $$$i$$$ (in column number $$$x$$$, you can collect at most $$$x$$$ boxes).

You want to level-up, so you want to gather as much XPs as possible.

* Columns are indexed $$$1$$$ based ($$$i$$$ : $$$1$$$ $$$2$$$ $$$3$$$ ... $$$m$$$)

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ $$$(1 \le n*m \le 10^6) , (0 \le k \le n*m)$$$, the dimensions of the grid and the maximum number of boxes you can take.

Follow $$$n$$$ lines, each containing $$$m$$$ separated integers: $$$ a_{i1} , a_{i2} , ... , a_{im}$$$ $$$(-10^9 \le a_{ij} \le 10^9)$$$, the value of each box in the grid.

Output

Print a single integer, the maximum amount of XPs you can get.

Examples
Input
1 1 1
1000
Output
1000
Input
5 2 10
8 6666
5 1000
6 8457
9699 88889
125 0
Output
107045
Input
3 3 6
2 -1 5
-2 3 3
4 5 6
Output
26