ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1869. Новогодний круиз

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

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
3
0 180 180
0 0 180
360 0 0
10
Автор задачи: Денис Дублённых
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2011