Треугольник чисел

Дан треугольник из чисел: в первой строке одно число, во второй два, и так далее.

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

В первой строке число $n$ от $1$ до $1000$. В следующих $n$ строках: в строке с номером $i$ ровно $i$ чисел от $-10^9$ до $10^9$.

Одно число.

Одной строки хватает и здесь, но обновлять её надо справа налево — иначе левый сосед успеет обновиться раньше, чем вы его прочтёте.