Hình vuông lớn nhất tổng nhỏ

Cho ma trận $A$ kích thước $n\times m$ gồm các số nguyên không âm, các phần tử $A_{i,j}$ với $1\le i\le n$, $1\le j\le m$.

Cho một ngưỡng $S$. Bạn cần tìm cạnh $k$ lớn nhất sao cho tồn tại một hình vuông kích thước $k\times k$ là sub-rectangle của $A$ với tổng các phần tử trong hình vuông đó không vượt quá $S$.

Hình vuông $0\times 0$ được coi là hợp lệ với tổng bằng $0$, do đó đáp án luôn không âm. Nếu không có hình vuông $k\times k$ nào với $k\ge 1$ thoả mãn, in ra $0$.

Dữ liệu vào

• Dòng đầu: ba số nguyên $n$, $m$, $S$.
• $n$ dòng tiếp theo, mỗi dòng có $m$ số nguyên mô tả ma trận $A$.

Dữ liệu ra

In ra một số nguyên duy nhất là cạnh $k$ lớn nhất tìm được.

Ràng buộc

• $1\le n,m\le 500$
• $0\le A_{i,j}\le {10}^9$
• $0\le S\le {10}^{18}$

Ví dụ

Ghi chú

Tổng của một hình vuông $k\times k$ có thể vượt quá phạm vi $32$-bit; hãy sử dụng kiểu số nguyên $64$-bit khi tính tổng.