Mê cung số

Nguồn: UVa Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một mê cung số được biểu diễn bởi một ma trận gồm $N$ hàng và $M$ cột. Mỗi ô của ma trận chứa một số nguyên từ $0$ đến $9$, biểu diễn chi phí phải trả khi đi vào ô đó.

Từ một ô, bạn chỉ có thể di chuyển sang một ô kề cạnh theo một trong bốn hướng:

• lên trên;
• xuống dưới;
• sang trái;
• sang phải.

Không được di chuyển theo đường chéo và không được đi ra ngoài mê cung.

Bạn bắt đầu tại ô ở góc trên bên trái, tức ô $(1,1)$, và cần đi đến ô ở góc dưới bên phải, tức ô $(N,M)$.

Chi phí của một đường đi bằng tổng giá trị của tất cả các ô mà đường đi đi qua, bao gồm cả ô bắt đầu $(1,1)$ và ô kết thúc $(N,M)$.

Hãy tìm chi phí nhỏ nhất có thể để đi từ ô $(1,1)$ đến ô $(N,M)$.

Minh họa

Xét mê cung gồm $4$ hàng và $5$ cột sau:

Trong ma trận trên:

• ô bắt đầu là $(1,1)$, có chi phí $0$;
• ô kết thúc là $(4,5)$, có chi phí $5$;
• từ mỗi ô chỉ có thể chuyển sang các ô chung cạnh với nó.

Ví dụ, từ ô $(2,3)$ có thể di chuyển đến các ô $(1,3)$, $(3,3)$, $(2,2)$ hoặc $(2,4)$.

Đối với mê cung minh họa này, chi phí nhỏ nhất để đi từ góc trên bên trái đến góc dưới bên phải là $24$.

Input

Dòng đầu tiên chứa số nguyên $N$, là số hàng của mê cung.

Dòng thứ hai chứa số nguyên $M$, là số cột của mê cung.

$N$ dòng tiếp theo mô tả ma trận chi phí. Dòng thứ $i$ chứa $M$ số nguyên

$a_{i,1},a_{i,2},\ldots,a_{i,M}$,

trong đó $a_{i,j}$ là chi phí của ô ở hàng $i$, cột $j$.

Các số trên cùng một dòng được phân cách bởi dấu cách.

Mỗi file Input chỉ chứa một mê cung.

Output

In ra một số nguyên duy nhất: chi phí nhỏ nhất để đi từ ô $(1,1)$ đến ô $(N,M)$.

Subtask

Trong tất cả các Subtask:

$0 \le a_{i,j} \le 9$.

Đặt $V=N\cdot M$ là tổng số ô của mê cung.

• Subtask 1 — 10% : $1 \le N,M \le 999$; $V \le 18$.
• Subtask 2 — 20% : $1 \le N,M \le 999$; $V \le 2500$.
• Subtask 3 — 30% : $1 \le N,M \le 999$; $V \le 2\cdot10^5$.
• Subtask 4 — 40% : $1 \le N,M \le 999$; $V \le 998001$.

Ví dụ

Ví dụ 1

Input

4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5

Output

24

Giải thích

Mê cung có $4$ hàng và $5$ cột.

Một đường đi đạt chi phí $24$ là:

$(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(4,3)\rightarrow(4,4)\rightarrow(4,5)$.

Các giá trị của những ô trên đường đi lần lượt là:

$0,3,1,4,5,4,2,5$.

Tổng chi phí bằng:

$$0+3+1+4+5+4+2+5=24.$$

Không tồn tại đường đi hợp lệ nào từ $(1,1)$ đến $(4,5)$ có tổng chi phí nhỏ hơn, vì vậy kết quả cần in là $24$.

Ví dụ 2

Input

1
6
0 1 2 3 4 5

Output

15

Giải thích

Mê cung chỉ có một hàng gồm $6$ ô.

Từ ô $(1,1)$ đến ô $(1,6)$, đường đi bắt buộc phải lần lượt đi qua:

$(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(1,4)\rightarrow(1,5)\rightarrow(1,6)$.

Tổng chi phí là:

$$0+1+2+3+4+5=15.$$

Do đó kết quả là $15$.