Падение по полю

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

Найдите наименьшую сумму чисел в посещённых клетках.

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

Одно число.