В жизни русского человека всегда есть место празднику. Особенно когда несколько поводов для празднования следуют один за другим — Новый год, Рождество, старый Новый год… Все отмечают эти праздники по-разному. Кому-то нравится побыть в кругу семьи или друзей, а кого-то, наоборот, тянет в путешествия. В компании «Сибирские железные дороги» решили совместить эти два варианта и запустили специальный круизный поезд «Бодун» по маршруту Владивосток--Москва--Владивосток. Этот поезд будет курсировать всего один раз в год — в новогодние праздники. В поезде будут созданы все условия для того, чтобы любой из праздников можно было отмечать вплоть до следующего. Ну, или до прибытия поезда в пункт назначения.

Спрос на билеты на данный поезд превзошёл все ожидания компании. Их продажу пришлось прекратить уже на третий день, поскольку иначе поезд, вмещающий всех желающих, не встал бы ни на один вокзал. Работники Сибирских железных дорог посчитали, сколько билетов продано на проезд между каждой парой станций, и теперь хотят определить, сколько вагонов должно быть в поезде, чтобы хватило мест для всех пассажиров.

В первой строке записано единственное целое число n — количество станций, на которых останавливается поезд при следовании в одну сторону (2 ≤ n ≤ 100). Станции пронумерованы числами от 1 до n в порядке следования поезда, Владивосток имеет номер один, Москва — номер n. Далее в n строках записана матрица a_ij размера n × n. Число a_ij равно количеству людей, купивших билет от станции i до станции j (0 ≤ a_ij ≤ 1 000; a_ii = 0). Все a_ij целые. Если i < j, то пассажиры, купившие билет от станции i до станции j, сядут на поезд, следующий из Владивостока в Москву, а если i > j, то на поезд, возвращающийся из Москвы во Владивосток.

Выведите единственное целое число — минимальное количество вагонов, которое должно быть в поезде, чтобы всем пассажирам хватило мест. В каждом вагоне ровно 36 мест.