Problem
Trong một bàn hình chữ nhật NxM (trong mỗi ô được viết một số nhất định), lúc đầu người chơi ở ô phía trên bên trái.
Trong một lần di chuyển, anh ta được phép di chuyển sang ô tiếp theo sang phải hoặc xuống dưới (không được di chuyển sang trái và lên trên).
Khi đi qua một ô, người chơi sẽ bị tính phí bằng c.u.
Cần phải tìm số lượng c.u. tối thiểu, bằng cách trả tiền mà người chơi có thể đến góc dưới bên phải.
Đầu vào:
- dòng đầu tiên chứa hai số N và M - kích thước bảng (\(1<=N<=20 \), \(1<=M<=20\));
- sau đó có N dòng số M trong mỗi - kích thước tiền phạt trong c.u. để đi qua các ô tương ứng (mỗi số từ 0 đến 100).
Đầu ra: in số tiền tối thiểu bạn có thể chi tiêu để nhận được ở góc dưới bên phải.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |