Громила Ральф вот уже 30 лет живёт в игровом автомате, и вы его можете увидеть на экране того самого автомата.
Сегодня Ральф гуляет по экрану, на котором отображается прямоугольное изображение, разбитое на N x N клеток. В каждой клетке находится тарелка с его любимыми блинчиками (на всех тарелках разное количество блинчиков). Ральф начинает перемещаться с левой нижней клетки прямоугольника. Съев все блинчики в текущей клетке, он перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, где больше блинчиков в тарелке (за пределами прямоугольника тарелок с блинчиками нет). В конце концов Ральф приходит в правую верхнюю клетку. Вам же предстоит определить, сколко всего блинчиков съел Ральф пока путешествовал по экрану. Блинчики в начальной и конечной клетках Ральф тоже съел с большим удовольствием.
Входные данные
Программа получает на вход в первой строке целое число N – размер изображения (2 <= N <= 10). В следующих N строках задаются через пробел числа, обозначающие количество блинчиков на тарелках, начиная с верхнего ряда и заканчивая нижним. Все числа – различные, натуральные, не превосходящие 100.
Выходные данные
Выведите одно число - количество блинчиков, которое съест Ральф, добравшись до правой верхней клетки.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
37 82
23 52
|
157
|