Chi phí robot tối thiểu

Bối cảnh và bài toán

Mỗi ô của lưới chứa chi phí vận hành không âm. Robot đi từ góc trên trái tới góc dưới phải bằng các bước xuống/phải và trả chi phí của mọi ô đi qua.

Yêu cầu

Tìm tổng chi phí nhỏ nhất.

Input

Dòng 1: n m; tiếp theo n dòng, mỗi dòng m số.

Output

In chi phí nhỏ nhất.

Ràng buộc

• 1 <= n,m <= 1000
• 0 <= a[i][j] <= 1000

Chấm điểm

Ví dụ 1

Input

2 3
1 2 3
4 5 1

Output

7

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

1 1
7

Output

7

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.