Hình vuông chẵn
Cho bảng chữ nhật $M$ hàng $N$ cột. Ô ở hàng thứ $i$, cột thứ $j$ là ô $(i,j)$, có giá trị $a_{i,j}$. Hãy tìm hình vuông có cạnh lớn nhất sao cho có ít nhất $K$ giá trị $a_{i,j}=1$.
Dữ liệu
- Dòng đầu tiên chứa ba số nguyên $M, N, K \ (1 \le M,N \le 3000; 1\le K\le M\times N)$;
- $M$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $a_{i,j} \ (|a_{i,j}|\le 1)$.
Kết quả
- Chiều dài lớn nhất.
Ví dụ
Ví dụ 1
input
3 4 3
1 1 0 0
0 1 0 1
1 1 1 0
output
2
Comments