Dijkstra trên bảng

Vương quốc Eldoria đang rơi vào hỗn loạn khi con rồng hắc ám Ragnarok trỗi dậy. Chỉ có viên ngọc huyền thoại tại vị trí R mới có thể phong ấn nó mãi mãi. Nhà thám hiểm Galen, xuất phát từ vị trí G, cần tìm đường đi với tổng độ khó nhỏ nhất để đến nơi.

Bản đồ Eldoria là một lưới \(n \times m\) gồm các ô chứa chữ số, mô tả mức độ khó khi di chuyển qua đó. Galen chỉ có thể di chuyển theo bốn hướng: trái, phải, lên, xuống. Hãy giúp anh ta tìm đường đi ít tốn sức lực nhất để đến được viên ngọc!

Input

Dữ liệu được nhập từ bàn phím với định dạng như sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 1000)\) --- kích thước bản đồ Eldoria.

• \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi \(m\) ký tự:

• Một chữ số (\(0-9\)) --- mức độ khó khi đi qua ô đó.

• Ký tự G --- vị trí của Galen (điểm xuất phát).
• Ký tự R --- vị trí của viên ngọc huyền thoại (điểm đích).

Output

In ra một số nguyên duy nhất --- tổng độ khó thấp nhất để đi từ vị trí G đến R. Nếu không thể tìm được đường đi, in -1.

Example

3 3
323
G9R
018

8