Cho ma trận A kích thước nxn gồm các số nguyên, ( 0 ≤ i < n, 0 ≤ j < n ).
Thao tác SHIFT tại hàng i ( 0 ≤ i < n ) sẽ dịch các số ở hàng i sang phải 1 vị trí
và số ở cột cuối cùng sẽ trở về đầu tiên.
Bạn có thể thực hiện SHIFT bao nhiêu lần cũng được.
Đặt Cj=A0,j+A1,j+..+A(n-1),j và M = max {Cj|0<=j < n } sau mỗi lần dịch chuyển.
Cj là tổng các số ở cột j.
Tìm giá trị bé nhất của M.
Input
Gồm một vài test, dòng đầu mỗi test là số nguyên n. n dòng tiếp theo
mỗi dòng chứa n số nguyên. Kết thúc các bộ test là số -1.
Giả thiết là 1 ≤ n ≤ 7 và |Ai,j| < 10^4.
Sample Input
2
4 6
3 7
3
1 2 3
4 5 6
7 8 9
-1
Output
Với mỗi bộ test, in ra giá trị nhỏ nhất của giá trị lớn nhất của tổng các
số trên 1 cột.
Sample output
11
15
RSS