Vào ngày Halloween, dinhwe2612 muốn trang trí căn phòng của mình bằng một dãy các quả bí ngô. Các quả bí ngô này được đánh số ~1, 2, 3, ... n~. Mỗi quả có một hình thù độc đáo riêng có quả mặt cười, quả khóc, quả giận dữ,... và cần được xếp thành một hàng.

Khi xếp những quả bí ngô này cạnh nhau thành một hàng, chúng sẽ có một độ hấp dẫn nhất định. Những cách xếp khác nhau sẽ có độ hấp dẫn khác nhau. dinhwe2612 đã tiến hành đánh giá độ hấp dẫn của cách xếp bằng cách đánh giá từng cặp bí ngô kề nhau: cậu xét một cặp bí ngô ~(i, j)~, độ hấp dẫn của cặp bí ngô này khi đứng liền kề nhau và ~i~ đứng trước ~j~ sẽ là ~a_{ij}~. Như vậy, độ hấp dẫn của một cách xếp sẽ là tổng độ hấp dẫn của tất cả các cặp bí ngô đứng kề nhau. (đọc ví dụ và giải thích để hiểu rõ hơn)

Vì muốn căn phòng của mình phải thật hấp dẫn, nên dinhwe2612 muốn độ hấp dẫn của cách xếp phải là lớn nhất. Trong lúc dinhwe2612 còn đang bận cày anime, các bạn hãy giúp cậu ấy tìm giá trị lớn nhất đó nhé.

Dữ liệu vào

• Dòng đầu tiên chứa số ~n~ - số lượng quả bí ngô cần sắp xếp.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên ~a_{i1}, a_{i2},..., a_{in}~ ~(|a_{ij}| \le 10^6, a_{ii} = 0)~ - thể hiện độ hấp dẫn của từng cặp bí ngô nếu để kề nhau theo thứ tự ~i \to j~.

Dữ liệu ra

Gồm một dòng duy nhất, ghi giá trị độ hấp dẫn lớn nhất mà dinhwe2612 có thể đạt được.

Giới hạn

• ~50\%~ số điểm có ~n \le 10~.
• ~50\%~ số điểm còn lại có ~n \le 18~.

Sample Input

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

Sample Output

29

Giải thích

Cách xếp tối ưu là ~2 \to 4 \to 5 \to 1 \to 3~. Độ hấp dẫn của cách xếp này là ~a_{24} + a_{45} + a_{51} + a_{13} = 8+8+8+5 = 29~.