Một trò chơi trí tuệ khác mà Đan đã làm là trò chơi chặn đường. Trò chơi diễn ra trên một mê cung được biểu diễn bằng lưới ô vuông kích thước \(m \times n\), các hàng của lưới được đánh số từ \(1\) đến \(m\), các cột của lưới được đánh số từ \(1\) đến \(n\), ô nằm giao giữa hàng \(i\) và cột \(j\) được gọi là ô \((i, j)\). Mỗi ô có thể là ô cấm (ô không được phép đi vào) hoặc là ô tự do (ô có thể đi vào). Một tên cướp đang ở ô \((1, 1)\) và cần di chuyển đến ô \((m, n)\), mỗi bước tên cướp có thể di chuyển sang một trong bốn ô chung cạnh là ô tự do. Nhiệm vụ của người chơi là cần đặt cảnh sát vào một số ô tự do để chặn đường không cho tên cướp đi được đến ô \((m, n)\), tên cướp không thể di chuyển vào ô có cảnh sát. Biết rằng có một số ô tự do có thể đặt cảnh sát, ví dụ nếu ô \((i, j)\) là ô có thể đặt cảnh sát thì sẽ mất chi phí \(c_{ij}\) \((1 \leq c_{ij} \leq 9)\).

Yêu cầu: Tính chi phí ít nhất để chặn được tên cướp không di chuyển được đến ô \((m, n)\).

Input

• Dòng đầu chứa hai số nguyên dương \(m, n\) \((m \times n > 1)\)
• Dòng thứ \(i\) \((1 \leq i \leq m)\) trong dòng \(m\) sau, mỗi dòng chứa một xâu độ dài \(n\) , kí tự thứ \(j\) \((1 \leq j \leq n)\) chỉ gồm các loại kí tự sau:
  • Kí tự # mô tả ô tả ô là ô cấm.
  • Kí tự 1 đến 9 mô tả ô là ô tự do và có thể đặt cảnh sát với chi phí tương ứng từ \(1\) đến \(9\).
  • Kí tự . mô tả ô là ô tự do và không được phép đặt cảnh sát.

Chú ý rằng ô \((1, 1)\) và ô \((m, n)\) luôn là ô tự do không được đặt cảnh sát.

Output

• Gồm một dòng chứa một số nguyên là chi phí ít nhất để đặt cảnh sát nhằm chặn tên cướp không di chuyển được đến ô \((m, n)\), nếu không tồn tại ghi \(-1\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m \leq 2; n \leq 1000\).
• Subtask \(2\) (\(40\%\) số điểm): \(m \times n \leq 2 \times 10^{3}\).
• Subtask \(3\) (\(30\%\) số điểm): \(m \times n \leq 2 \times 10^{5}\).

Example

2 4
.#.1
..2.

2

2 4
....
..1.

-1