Малюк Смурф хоче д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