Trong rạp chiếu phim có ~N~ ghế dành cho ~N~ vị khách.

Mỗi người lần lượt vào rạp xem phim và phải ngồi vào đúng chỗ của mình (người vào thứ ~i~ phải ngồi ghế thứ ~i)~.

Tuy nhiên, có một ông khách VIP vào đầu tiên và được giành lấy một ghế bất kì. Mỗi người tiếp theo khi vào rạp thì ý thức hơn nên sẽ ngồi vào đúng chỗ (nếu ghế của họ chưa có người ngồi). Nhưng nếu chỗ của họ đã bị lấy mất thì họ được quyền chọn ~1~ ghế khác bất kì.

Ta biết ~C[i~, ~j]~ là độ hài lòng của vị khách thứ ~i~ khi ngồi vào ghế thứ ~j~. Hãy tính giá trị lớn nhất có thể của tổng độ hài lòng của ~N~ vị khách.

Input

• Dòng đầu tiên là số nguyên dương ~N~ ~(1 \le N \le 1000)~;
• Dòng thứ ~i~ (trong ~N~ dòng tiếp theo) gồm ~N~ số nguyên. Số thứ ~j~ cho là giá trị ~C[i~, ~j]~ ~(|C[i, j]| \le 1\,000\,000\,000)~;

Output

• Một số nguyên duy nhất là tổng lớn nhất có thể đạt được.

Sample Input

4
2 6 8 6 
5 0 6 7 
8 0 1 9 
2 7 2 4

Sample Output

24