Cinema

The main movie theater of the city has a single auditorium with rows of padded seats. Each seat has a comfort value, which is a non-negative integer. A seat with a larger comfort value is more comfortable.

A row can only be entered from the left side of the auditorium. The seats in a row are numbered 1 to $m$ from left to right. When a person enters a row, they sit on the most comfortable seat that is free and accessible to them. If they sit at seat $i$, every person who comes later is blocked from seats $i+1$ to $m$. If several free and accessible seats tie for the highest comfort value, the person sits on the leftmost one.

The owner plans to raise the comfort values of some seats to attract more audiences. Raising a seat's comfort value by one unit costs a fixed amount. The total increase across all seats must not exceed $k$. Find the way to raise comfort values by at most $k$ units in total that gives the maximum number of audiences in the auditorium.

The first line contains three non-negative integers $n$, $m$, and $k$, where $n$ is the number of rows, $m$ is the number of seats in each row, and $k$ is the total comfort increase allowed. The constraints are $1 \le n \cdot m \le 3 \times 10^5$ and $0 \le k \le 10^{12}$.

Each of the next $n$ lines contains $m$ non-negative integers, each at most $10^6$, giving the comfort values of the seats in that row from left to right.

Print a single line containing the maximum number of audiences.