Cho ma trận ~A~ kích thước nxn gồm các số nguyên, ~(0 \leq~ ~i < n~, ~0 \leq~ ~j < n)~.

Thao tác SHIFT tại hàng ~i~ ~(0 \leq~ ~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.

$$A_{i, 0} \rightarrow A_{i, 1} \rightarrow A_{i, 2} \rightarrow \dots \rightarrow A_{i, n - 2} \rightarrow A_{i, n - 1}$$ $$\nwarrow \\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_\\_ \swarrow$$

Bạn có thể thực hiện SHIFT bao nhiêu lần cũng được.

Đặt ~C_j = A_{0, j} + A_{1, j} +~ ...~+ A_{n-1, j}~

và ~M = max \{C_j|0 \le j < n\}~ sau mỗi lần dịch chuyển.

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~.

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.

Giới hạn

• ~1 \leq n \leq~ ~7~.
• ~|A_{i, j}| < 10^{4}~.

Sample Input

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

Sample Output

11
15