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

В примере ниже отчетливо видно, что выделенный треугольник удовлетворяет условию, т.к. его сумма равна −42.

Мы собираемся сделать такой треугольный массив с одной тысячей строк, поэтому нам необходимо сгенерировать 500500 псевдослучайных числа s_k в диапазоне ±2¹⁹, воспользовавшись определенным типом генератора случайных чисел (известен как "линейный конгруэнтный генератор") следующим образом:

t := 0
при k = 1 до k = 500500:
    t := (615949*t + 797807) modulo 2²⁰
    s_k := t−2¹⁹

Таким образом: s₁ = 273519, s₂ = −153582, s₃ = 450905 и т.д.

После этого наш треугольный массив формируется из полученных псевдо-случайных чисел следующим образом:

Под-треугольники можно начинать с любого элемента массива и продолжать их вниз настолько, насколько это необходимо (выбирая два элемента на следующей строке, три элемента на идущей через одну строке и т.д.).
"Сумма под-треугольника" определяется как сумма всех его элементов.
Найдите наименьшую возможную сумму под-треугольника.