Hai quân xe được đặt tại hai ô khác nhau trên một bàn cờ vua có ~N \times N~ ô. Mỗi ô của bàn cờ có một giá trị từ ~0~ đến ~1000~.

Một ô trong bàn cờ được gọi là bị tấn công nếu ô đó cùng hàng hoặc cùng cột với ít nhất một quân xe. Hai ô vuông có chứa quân xe được xem như không bị tấn công .

Bài toán đặt ra là tìm cách đặt hai quân xe lên bàn cờ, để tổng giá trị các ô bị tấn công là lớn nhất .

Input

• Dòng ~1~: Số nguyên dương ~N~ ~(2 \leq N \leq 300)~.
• ~N~ dòng tiếp theo, mỗi dòng gồm ~N~ số. Đây là giá trị của các ô trên bàn cờ.

Output

• Tổng lớn nhất tìm được.

Giới hạn

• Có ~60\%~ số test, ~2 \leq N \leq 100~

Sample Input 1

3
0 1 4
3 0 2
1 4 1

Sample Output 1

15

Sample Input 2

4
0 1 1 1
1 0 4 3
0 1 3 5
0 0 2 5

Sample Output 2

23

Sample Input 3

5
4 2 2 3 3
4 2 1 4 0
1 3 4 0 1
4 3 0 2 3
0 0 3 0 4

Sample Output 3

40

Note

• Vị trí đặt hai quân xe trong ví dụ ~1~ là ~(1~, ~1)~ và ~(2~, ~2)~
• Vị trí đặt hai quân xe trong ví dụ ~2~ là ~(1~, ~3)~ và ~(1~, ~4)~
• Vị trí đặt hai quân xe trong ví dụ ~3~ là ~(2~, ~5)~ và ~(4~, ~3)~