Nate vừa mua được một mảnh đất ở thành phố ABC để xây nhà.

Khu đất của Nate có kích thước ~n \times m~ mét vuông, với ~n~ là chiều dài, ~m~ là chiều rộng. Cậu muốn xây một ngôi nhà có dạng hình vuông có chiều dài là số nguyên dương có diện tích lớn nhất có thể và nằm hoàn toàn trong khu đất mà Nate đã mua. Tuy nhiên, để xây được một ngôi nhà an toàn, phần đất được chọn phải đạt được một số tiêu chí nhất định.

Nate đã tiến hành một cuộc khảo sát trên mảnh đất bằng cách chia mảnh đất thành các ô vuông nhỏ, mỗi ô có diện tích ~1 \times 1~ ~(m^2)~ và đưa ra số liệu về độ nguy hiểm của mỗi ô trên mảnh đất này. Độ nguy hiểm của ô ở hàng thứ ~i~, cột thứ ~j~ của mảnh đất là ~a_{(i,j)}~. Để một mảnh đất có kích thước ~a \times a~ ~(m^2)~ đạt tiêu chuẩn xây nhà, tổng độ nguy hiểm của tất cả các ô trong mảnh đất phải không vượt quá ~k~. Nói cách khác, một mảnh đất có kích thước ~a \times a~ ~(m^2)~ có góc trên bên trái là ô ~a_{(x_1,y_1)}~ và góc dưới bên phải là ô ~a_{(x_1+a-1,y_1+a-1)}~ (~1 \leq x_1 \leq m; 1 \leq y_1 \leq n~) đạt tiêu chuẩn xây nhà khi và chỉ khi điều kiện sau thỏa mãn:

$$\sum_{i=x_1}^{x_1+a-1} \sum_{j=y_1}^{y_1+a-1} a_{(i,j)} \leq k$$

Mảnh đất của Nate mua rất lớn nên cậu nhờ bạn giúp. Hãy tìm chiều dài nhà ~x~ lớn nhất mà tồn tại một mảnh đất trong khu đất đã mua của Nate có thể xây nhà chiều dài ~x~. Nếu không tồn tại bất kỳ mảnh đất với bất kỳ kích thước nào có thể xây nhà, in ra 0.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương ~m,n,k~ (~1 \leq m,n \leq 2000~; ~k \leq 10^9~) lần lượt là chiều rộng, chiều dài của khu đất và độ nguy hiểm tối đa mà ngôi nhà có thể có.
• ~m~ dòng tiếp theo, dòng thứ i gồm ~n~ số nguyên không âm ~a_{(i,1)}, a_{(i,2)}, \ldots, a_{(i,n)}~ là độ an toàn của từng ô của khu đất (~0 \leq a_{(i,j)} \leq 10^9~).

Dữ liệu ra:

• Một số nguyên ~x~ là đáp án của bài toán.

Input:

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

Output:

3

Giải thích:

Mảnh đất được tô vàng là mảnh đất thỏa mãn.

Ràng buộc:

• ~25\%~ số điểm có ~m,n \leq 10~
• ~25\%~ số điểm khác có ~m,n \leq 500~
• ~50\%~ số điểm còn lại không có ràng buộc gì thêm.