D. Рождественский экспресс

Рождественский экспресс — это поезд, который может доставить любого по кольцевому метро Северного полюса. Кольцевое метро состоит из $n$ станций, пронумерованных от $1$ до $n$. Экспресс будет останавливаться на станциях в порядке $1,2,\dots ,n,1,2,\dots ,n,1,2,\dots$ и так далее.

Согласно статистике за последние два года, Дед Мороз выяснил, что каждый раз, когда поезд останавливается на станции с номером $i$, на него садятся $a_{i,j}$ эльфов, которые выйдут на станции с номером $j$ для каждого $j$ ($j\ne i$) от $1$ до $n$. Деду Морозу необходимо узнать, какое минимальное количество мест должно быть в поезде, чтобы удовлетворить потребности жителей полюса.

Предполагается, что при остановке на любой станции пассажиры сначала выходят из поезда, а затем другие пассажиры заходят. Вам предстоит помочь Деду Морозу в этом вопросе.

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

Первая строка содержит одно целое число $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$.

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

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

Примеры

Примечание

Если поезд может перевозить только восемь пассажиров одновременно, то не все эльфы смогут уместиться в нем; девяти мест в поезде достаточно, чтобы всем эльфам хватило места.