Thành phố IOI là lưới chữ nhật gồm \(H\) hàng từ bắc xuống nam và \(W\) cột từ tây sang đông. Ô ở hàng \(i\), cột \(j\) được ký hiệu \((i,j)\). Một lễ hội lớn đang diễn ra và một số ô có quầy bán các loại bánh kẹo khác nhau. Không có quầy tại \((1,1)\), \((H,W)\) hay các ô chung cạnh với hai ô đó.

JOI-kun đi từ \((1,1)\) tới \((H,W)\), chỉ đi về đông hoặc nam. Mỗi khi vào một ô, cậu lần lượt thực hiện:

1. Nếu ô hiện tại có quầy bán loại bánh kẹo cậu chưa mua, cậu mua tại quầy đó.
2. Nếu các ô chung cạnh với ô hiện tại có những quầy bán loại bánh kẹo cậu chưa mua, cậu gọi người bán từ tất cả các quầy ấy ngoại trừ đúng một quầy và mua bánh kẹo của họ.

Cậu không mua cùng một loại bánh kẹo nhiều lần. Vì mọi quầy bán loại khác nhau, hãy tìm tổng số tiền nhỏ nhất cậu phải trả trên một đường đi hợp lệ.

Dữ liệu vào

• Dòng đầu chứa \(H,W\) (\(3\le H,W\le1000\)).
• \(H\) dòng tiếp theo, mỗi dòng là xâu dài \(W\). Ký tự . nghĩa là không có quầy; một chữ số từ 1 đến 9 là giá bánh kẹo tại quầy đó.

Dữ liệu ra

In ra tổng tiền nhỏ nhất.

Chấm điểm

Có 5 bộ dữ liệu, mỗi bộ trị giá 20 điểm. Trong dữ liệu 1, số ô có quầy không vượt quá 20. Các dữ liệu còn lại không có ràng buộc bổ sung.

Ví dụ

5 5
..483
.59.9
3.866
79...
4.8..

20

12 10
..498522.4
.633527629
54.4621596
634.213458
1924518685
7739539767
276155.3.6
87716372.2
.858877595
7998739511
3438.5852.
568.9319..

63

Nguồn

Kỳ thi sơ loại Olympic Tin học Nhật Bản 2015/2016, bài 6.