eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

D. Різдвяний експрес

D. Різдвяний експрес

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Різдвяний експрес — потяг, що може доставити будь-кого по кільцевому метро північного полюсу. Кільцеве метро містить 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. У Дідусика Морозика важливе запитання — яка мінімально можлива кількість місць може бути у потязі, щоб задовольнити потреби жителів полюсу?

Ви можете вважати, що при зупинці на будь-якій станції пасажири спочатку виходять з потяга, а лише потім інші пасажири заходять до нього. Звісно, допомагати Морозику доведеться Вам.

Входные данные

Перший рядок містить одне ціле число 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.

Выходные данные

Виведіть одне ціле число — відповідь на задачу.

Пример

Входные данные #1
3
0 2 3
2 0 4
3 0 0
Выходные данные #1
9

Примечание

Якщо потяг зможе перевозити лише вісьмох пасажирів одночасно, то не всі ельфи зможуть поміститись у нього; дев'ять місць у потязі достатньо, щоб ельфам вистачало місця.

Автор Ihor Barenblat
Источник Ukrainian Olympiad in Informatics 2021, II Stage