Cho ma trận vuông ~n \times n~ gồm các số nguyên dương và số ~R~. Tìm số nguyên lớn nhất ~k~ sao cho tồn tại một hình vuông con ~k \times k~ có tổng không vượt quá ~R~.

Dữ liệu vào

Dòng đầu chứa ~n~ và ~R~.

~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên.

Dữ liệu ra

In giá trị ~k~ lớn nhất. Nếu không có hình vuông ~1 \times 1~ nào thỏa mãn, in ~0~.

Giới hạn

~1 \le n \le 1000~, ~1 \le R \le 10^{18}~, ~1 \le A_{i,j} \le 10^{9}~.

V? d?

Input

1 4
5

Output

0