|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Вася решил заняться постройкой самодвижущегося робота-уборщика, но с удивлением обнаружил, что элементы управления, которые он купил на рынке позволяют двигаться роботу только вперед и/или налево. Продавца который продал ему элементы управления он уже не нашел, а денег на новые у него нет.
Пришлось Васе строить робота-уборщика из того, что у него есть. Но его работа должна быть как минимум эффективная, поэтому его робот должен за один проход убирать максимальное количества мусора в квадратной комнате. Помогите Васе составить программу, которая за один проход уберет максимальное количество мусора. Начинается работа всегда с левого верхнего угла, а заканчивается в нижнем правом углу, где Вася его начинает разбирать.
Формат входных данных
Первая строка содержит число N (1≤N≤100) - размер комнаты.
Далее следует N строк, каждая из которых содержит N целых чисел, которые показывают количество мусора, которое может собрать робот-уборщик в указанной точке.
Формат выходных данных
Выведите единственное число – количество мусора, которое собрал робот-уборщик (целое, положительное число).
|
Ввод 1
|
Ввод 2
|
3
6 -1 0
0 0 31
0 1 2
|
4
2 1 3 1
4 0 1 1
1 1 2 1
0 1 2 7
|
|
Вывод 1
|
Вывод 2
|
|
39
|
19
|
Для отправки решений необходимо выполнить вход.
|