Problems
D. Різдвяний експрес
D. Різдвяний експрес
Різдвяний експрес~--- потяг, що може доставити будь-кого по кільцевому метро північного полюсу. Кільцеве метро містить $n$ станцій, пронумерованих цілими числами від $1$ до $n$. Експрес зупинятиметься на станціях з номерами $1,2,\dots,n,1,2,\dots,n,1,2,\dots$, і так далі...
Опираючись на статистику останніх двох років, Дідусик Морозик визначив, що кожного разу, коли потяг зупинятиметься на станції з номером $i$ для кожного $j$ ($j\ne i$) від $1$ до $n$ у потяг сядуть $a_{i,j}$ ельфів, які вийдуть на станції з номером $j$. У Дідусика Морозика важливе запитання~--- яка мінімально можлива кількість місць може бути у потязі, щоб задовольнити потреби жителів полюсу?
Ви можете вважати, що при зупинці на будь-якій станції пасажири спочатку виходять з потяга, а лише потім інші пасажири заходять до нього. Звісно, допомагати Морозику доведеться Вам.
\InputFile
Перший рядок містить одне ціле число $n$ ($2\le n\le 500$).
Кожен з наступних $n$ рядків містить по $n$ цілих чисел $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($0\le a_{i,j}\le 500$). Всі значення $a_{i,i}$ рівні $0$.
\OutputFile
Виведіть одне ціле число~--- відповідь на задачу.
\Note
Якщо потяг зможе перевозити лише вісьмох пасажирів одночасно, то не всі ельфи зможуть поміститись у нього; дев'ять місць у потязі достатньо, щоб ельфам вистачало місця.
Input example #1
3 0 2 3 2 0 4 3 0 0
Output example #1
9