以下题面由 AI 翻译。

你的电脑老是有线头，导致你经常头痛。因此，你决定购买一台新型的平价TFT显示器。走进电脑商店时，你发现店内已经挤满了顾客。

实际上，这个商店客满，走进去需要弯腰。由于你希望尽快完成未竟的SPOJ任务回家，你想尽量避开人群。仔细观察后发现，某些商店区域比较空旷。因此，你意识到有可能在合理的时间内找到一条最短路径返回家中。

你画出商店的布局草图，但即使如此，找到最短路径仍然很棘手。拿出笔记本开始编写程序，以帮助你找到回家的最短路径。

输入格式

第一行给出商店的宽度w和高度h（均不超过25）。

接下来的h行每行包含w个字符。字母X表示货架，S表示你的起始位置，D表示目的地（即你面前的显示器）。所有空闲区域用1到9之间的数字表示，表示经过该区域所需的时间（秒）。

多个测试用例之间由一个空白行分隔。输入以宽度和高度均为0时结束。

输出格式

对于每个测试用例，输出到达目的地所需的最短时间（秒）。每个测试用例单独一行。只能垂直或水平移动。当然，所有移动必须在网格内进行。你总能找到一条通向目的地的路径。

示例

输入样例:
4 3
X1S3
42X4
X1D2
5 5
S5213
2X2X5
51248
4X4X2
1445D
0 0
输出样例:
4
23