Bài 3. Đường đi có chi phí nhỏ nhất

Mô tả

Cho ma trận chi phí a[i][j] gồm các số nguyên không âm. Bạn xuất phát từ ô (1,1) và cần đi tới ô (n,m).

Mỗi bước bạn được phép đi:

• sang phải (i, j+1)
• xuống dưới (i+1, j)
• chéo xuống phải (i+1, j+1)

Hãy tìm chi phí nhỏ nhất của một đường đi từ đầu đến cuối.

Input

• Dòng đầu ghi hai số nguyên n, m.
• n dòng tiếp theo, mỗi dòng gồm m số nguyên a[i][j].

Output

In ra chi phí nhỏ nhất.

Giới hạn

• 1 <= n, m <= 1000 nếu không có ghi chú khác.
• Dữ liệu bảo đảm phù hợp với kiểu 64-bit signed integer nếu bài yêu cầu tổng hoặc chi phí.

Subtask

• Subtask 1 (30%): 1 <= n, m <= 30.
• Subtask 2 (30%): không dùng bước chéo vẫn cho đáp án tối ưu.
• Subtask 3 (40%): 1 <= n, m <= 1000.

Ví dụ

Input

3 3
1 2 3
4 8 2
1 5 3

Output

8