e-olymp
Задачи

Стек шаров

Стек шаров

Телеканал XYZ разрабатывает новое игровое шоу, в котором участники должны сделать некоторый выбор чтобы получить приз. Игра состоит из треугольного стека шаров, на каждом из которых записано целочисленное значение, как показано ниже на примере.

prb5741

Участник должен выбрать набор шаров, и его призом будет сумма чисел на них. Участник может взять шар, только если он берет все шары, находящиеся непосредственно над ним. Это может потребовать снятия дополнительных шаров по описанному правилу. Участник может не взять ни одного шара, в таком случае его приз будет равным нулю.

Директор телешоу заинтересован в том, чтобы участник получил максимальный приз для заданного стека. Так как он является Вашим босом, то попросил Вас решить эту задачу.

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

Каждый тест задается в нескольких строках. Первая строка содержит количество рядов N (1 N 1000) в стеке. i-ая из следующих N строксодержит i целых чисел Bij (-105Bij105 для 1 j i N); значение Bij равно числу, записанному на j-ом шаре в i-ом ряду стека (первый ряд - самый верхний, в каждом ряду первым шаром является самый левый).

За последним тестом следует строка, содержащая один ноль.

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

Для каждого теста вывести в отдельной строке целое число - максимальный приз, который может получить участник игры для заданного стека шаров.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
4
3
-5 3
-8 2 -8
3 9 -2 7
2
-2
1 -10
3
1
-5 3
6 -4 1
0
Выходные данные
7
0
6
Источник ACM ICPC Latin America 2011, November 4th-5th, 2011