K. MnTm
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

AAlikhan and $$$k$$$ of his friends are going to a concert by AAdo. The concert hall can be represented as a table of $$$n$$$ rows and $$$m$$$ columns (the price of a seat in row $$$i$$$ and column $$$j$$$ is equal to $$$c_{i,j}$$$), where the first row is closest to the stage, and the last row is farthest from the stage. Each cell of the table is one seat. Seats within the same column are priced in descending order from the first row to the last (the closer to the stage, the more expensive). It can be considered that the stage is on row $$$0$$$. AAlikhan and his friends want to buy one seat each so that they spend no more than $$$B$$$ betabucks in total and their seats form one connected component. They also all dream of seeing AAdo's face, so they want to sit so that the farthest friend is as close to the stage as possible. Find the row of the farthest friend.

The formation of one connected component means that all occupied seats must be connected to each other horizontally or vertically. This means that from any occupied seat you can get to any other occupied seat by moving horizontally or vertically through adjacent occupied seats.

It is guaranteed that AAlikhan will always have a way to buy $$$k+1$$$ seats.

Input

The first line of the input contains three integers $$$n, m, k(1 \le n,m \le 100,0 \le k \lt min(100,n * m))$$$ — the number of rows, columns in the table and the number of AAlikhan's friends.

The second line contains one integer $$$B(1 \le B \le 10^9)$$$ — the number of betabucks AAlikhan has.

The next $$$n$$$ lines contain $$$m$$$ integers each, describing the matrix $$$c$$$. In the $$$i$$$-th of these lines, the prices of tickets in the $$$i$$$-th row are written $$$c_{i,1},c_{i,2},...c_{i,m}(1 \le c_{i,j} \le 10^5)$$$. It is guaranteed that the prices of seats within the same column strictly decrease as they move away from the stage.

Output

Output one integer — the answer to the problem.

Examples
Input
3 3 1
5
3 6 9
2 5 8 
1 4 8
Output
2
Input
3 3 8
45
9 8 7
6 5 4
3 2 1
Output
3