Телеканал XYZ разрабатывает новое игровое шоу, в котором участники должны сделать некоторый выбор чтобы получить приз. Игра состоит из треугольного стека шаров, на каждом из которых записано целочисленное значение, как показано ниже на примере. \includegraphics{https://static.e-olymp.com/content/ed/edc5015bf33fa9baa7d0ee816d2614acfc09808d.jpg} Участник должен выбрать набор шаров, и его призом будет сумма чисел на них. Участник может взять шар, только если он берет все шары, находящиеся непосредственно над ним. Это может потребовать снятия дополнительных шаров по описанному правилу. Участник может не взять ни одного шара, в таком случае его приз будет равным нулю. Директор телешоу заинтересован в том, чтобы участник получил максимальный приз для заданного стека. Так как он является Вашим босом, то попросил Вас решить эту задачу. \InputFile Каждый тест задается в нескольких строках. Первая строка содержит количество рядов \textbf{N }(\textbf{1 }≤ \textbf{N }≤ \textbf{1000}) в стеке. \textbf{i}-ая из следующих \textbf{N }строк\textbf{ }содержит \textbf{i} целых чисел \textbf{B_ij} (\textbf{-10^5} ≤ \textbf{B_ij} ≤ \textbf{10^5} для \textbf{1 }≤ \textbf{j }≤ \textbf{i }≤ \textbf{N}); значение \textbf{B_ij} равно числу, записанному на \textbf{j}-ом шаре в \textbf{i}-ом ряду стека (первый ряд - самый верхний, в каждом ряду первым шаром является самый левый). За последним тестом следует строка, содержащая один ноль. \OutputFile Для каждого теста вывести в отдельной строке целое число - максимальный приз, который может получить участник игры для заданного стека шаров.