Tết lại sắp về, không khí rộn ràng đang lan tỏa khắp Việt Nam, gia đình bạn cũng bắt đầu tất bật chuẩn bị một bàn tiệc Tết thật đầy đặn để đón chào năm mới. Trên bàn, các món ăn được sắp xếp gọn gàng thành một bàn vuông có kích thước \(N \times N\). Mỗi ô trên bàn có ký hiệu là \(a_{ij}\), là số món ăn được bày tại ô ở vị trí hàng \(i\), cột \(j\). Mỗi ô trên bàn là một món ăn đặc trưng ngày Tết như bánh chưng, bánh tét, chả lụa, thịt kho tàu,...

Để bữa tiệc thêm phần thú vị, gia đình bạn đã nảy ra một ý tưởng độc đáo: Tìm một số nguyên dương \(M\) nhỏ nhất sao cho tất cả các mâm cỗ có kích thước \(M \times M\) (là một phần nhỏ của bàn tiệc \(N \times N\) nói trên) có tổng số món ăn trên mâm đạt ít nhất là \(K\). Biết rằng các mâm cỗ này có thể đặt ở bất kỳ đâu trên bàn, kể cả khi biên của mâm cỗ nằm trùng với biên của bàn.

Yêu cầu: Bạn hãy viết chương trình tính toán và tìm ra số nguyên dương \(M\) phù hợp nhất với đề bài.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(K\) \((1 \le N \le 5000,1 \le K \le 2 \times 10^9)\).
• Dòng tiếp theo chứa một bàn ăn chứa \(N \times N\) số nguyên \(a_{ij}\) \((0 \le a_{ij} \le 50)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài, nếu không tìm ra đáp án phù hợp thì in ra -1.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(N \le 20\).
• Subtask \(2\) (\(10\%\) số điểm): Có \(N \le 100\).
• Subtask \(3\) (\(20\%\) số điểm): Có \(N \le 500\).
• Subtask \(4\) (\(30\%\) số điểm): Có \(N \le 2000\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 15
2 3 5 8
4 1 6 2
9 7 3 1
5 8 4 6

3