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