영화관

이 도시의 주 영화관에는 푹신한 좌석이 줄지어 있는 상영관이 하나 있다. 각 좌석에는 0 이상의 정수인 편안함 값이 있다. 편안함 값이 클수록 더 편한 좌석이다.

줄은 상영관의 왼쪽에서만 들어갈 수 있다. 한 줄의 좌석은 왼쪽부터 1번에서 $m$번까지 번호가 매겨져 있다. 사람이 줄에 들어서면, 그 사람이 앉을 수 있는 빈 좌석 중 가장 편안한 좌석에 앉는다. 좌석 $i$에 앉으면, 이후에 들어오는 사람은 $i+1$번부터 $m$번까지 좌석에 앉을 수 없다. 앉을 수 있는 빈 좌석의 편안함 값이 가장 큰 좌석이 여럿이면 가장 왼쪽 좌석에 앉는다.

주인은 관객을 더 많이 모으려고 일부 좌석의 편안함 값을 올리려 한다. 좌석의 편안함 값을 1단위 올리는 데는 정해진 비용이 든다. 모든 좌석에서 올리는 값의 합은 $k$를 넘을 수 없다. 편안함 값을 전체적으로 최대 $k$단위까지 올려서 상영관의 관객 수를 최대로 만드는 방법을 구하라.

첫 줄에 음이 아닌 정수 $n$, $m$, $k$가 주어진다. $n$은 줄의 개수, $m$은 한 줄의 좌석 수, $k$는 모든 좌석의 편안함 값을 올릴 수 있는 총량이다. 제약 조건은 $1 \le n \cdot m \le 3 \times 10^5$이고 $0 \le k \le 10^{12}$이다.

이어지는 $n$개의 줄에는 각각 $m$개의 음이 아닌 정수가 주어진다. 각 값은 $10^6$ 이하이며, 해당 줄의 좌석 편안함 값을 왼쪽부터 차례대로 나타낸다.

관객 수의 최댓값을 한 줄에 출력한다.