Дешёвая дорога с диагональю

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

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

Одно число.