Một người lính đánh thuê cần di chuyển qua một khu vực nguy hiểm được mô phỏng bởi một lưới chữ nhật kích thước ~N \times M~. Người lính xuất phát từ góc trên cùng bên trái ở tọa độ ~(1, 1)~ và cần đi đến điểm tập kết ở góc dưới cùng bên phải tại tọa độ ~(N, M)~.

Tại mỗi ô ~(i, j)~ trên lưới, người lính sẽ phải tiêu tốn một mức năng lượng (hoặc tiền bạc) là ~C_{i, j}~ để có thể bước vào ô đó. Từ một ô, người lính chỉ có thể di chuyển sang 4 ô kề cạnh (Lên, Xuống, Trái, Phải). Tổng chi phí của hành trình được tính bằng tổng chi phí của tất cả các ô trên đường đi (bao gồm cả ô xuất phát ~(1, 1)~ và ô đích ~(N, M)~).

Hãy tìm một đường đi sao cho tổng chi phí (năng lượng) tiêu tốn là nhỏ nhất.

Gợi ý: Thuật toán BFS thông thường bằng Queue chỉ đúng khi chi phí ở mọi ô bằng nhau. Với chi phí khác nhau, hãy sử dụng Thuật toán Dijkstra kết hợp Hàng đợi ưu tiên nhỏ nhất (Min-Heap).

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ (~1 \le N, M \le 500~).
• ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên không âm ~C_{i, j}~ (~0 \le C_{i, j} \le 10^5~) thể hiện chi phí bước vào ô ~(i, j)~. Hai số liên tiếp cách nhau một khoảng trắng.

Kết quả

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để đi từ ~(1, 1)~ đến ~(N, M)~.

Ví dụ

Input

3 3
1 3 1
1 5 1
4 2 1

Output

7

Giải thích

Thay vì đi đường chéo xuống (chi phí ~1 + 5 + 1 = 7~ nhưng không được đi chéo) hoặc đi theo rìa trái-dưới (chi phí ~1 + 1 + 4 + 2 + 1 = 9~), người lính chọn đi theo đường vòng sang phải: ~(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)~. Tổng chi phí tương ứng: ~1 + 3 + 1 + 1 + 1 = 7~.