Малюк Смурф хоче дiстатися до Смурфетки i для цього йому треба подолати дорогу переповнену перешкодами та непрохiдними чагарниками. Для подолання перешкод малюк буде втрачати енергiю i тому йому треба знайти найлегший шлях. Татко Смурф завдяки своїм магiчним здiбностям створив план лiсу iз вказiвкою витрат енергiї при проходженнi кожного квадрата. Тепер Малюку Смурфу треба знайти марштур з найменшими витратами енергiї.

Формат вхідних даних

Перший рядок мiстить ширину \(w\) i висоту \(h\) плану. Жоден розмiр не перевищує 25.

Наступнi \(h\) рядкiв мiстять \(w\) символiв кожен. Лiтера \(X\) вказує непрохiдний квадрат, лiтера \(S\) позначає положення малюка Смурфа, а лiтера \(D\) - квадрат, у якому знаходиться Смурфетка. Прохiднi квадрати позначенi цифрами вiд 1 до 9, що означають кiлькiсть енергiї, необхiдної для проходження цього квадрата.

Iснує багато тестових випадкiв, якi роздiляються порожнiм рядком. Введення даних закiнчується шириною та висотою, рiвною 0 0.

Багато у нашiй задачi - не бiльше 1000.

Формат вихідних даних

Ваша програма повинна вивести мiнiмальну кiлькостi енергiї, яка необхiдна малюку Смурфу для подорожi. Кожен тест виводити в окремому рядку. Рухатися по плану можна лише вертикально та горизонтально. Завжди iснує спосiб дiстатися до квадрату Смурфетки.

Приклад вхідних даних

4 3
X1S3
42X4
X1D2

5 5
S5213
2X2X5
51248
4X4X2
1445D

0 0

Приклад вихідних даних

4
23