该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Kaf的下一堂课就要开始了，但是他在教学楼里迷路了。你需要帮助他在教学楼里找到他的下一个教室。

教学楼是一个 $r$ 行 $c$ 列的二维网格。教学楼中的每一个单元格可能是一堵墙，也可能是空的。空的单元格可能被零个或多个学生占据(教学楼里也可能有除Kaf之外的学生)。所有学生(包括Kaf)不能穿墙，其中有一个单元格是Kaf的教室入口。

初始的网格，包括你的初始位置、教室入口和所有其他学生的初始位置，都会交给你。下面是这样一个网格示例(第一个样例)：

移动

学生(包括Kaf)可以在教学楼里移动。在一次移动中，学生可以进行以下操作之一：

• 什么也不做。
• 从当前单元格移动到四个相邻单元格之一(如果两个单元格共用一条边，则为相邻)。注意，学生不能穿墙。
• 如果Kaf位于教室入口，他可以进入教室。只有Kaf可以执行此操作，其他所有学生都不能进入教室。

在Kaf每次移动后，其他每个学生也会同时移动(每个学生选择移动的方式可能不同)。

如果Kaf和 $t$ $(t > 0)$ 个学生位于同一个单元格，那么这次就会发生 $t$ 次相遇(因为Kaf会和这 $t$ 个学生每个人相遇一次)。相遇后，这 $t$ 个学生都会离开教学楼去。

请注意，在Kaf进入教室的那一刻，就不能再与其他学生相遇了，即使紧接着又有一个学生移动到了教室入口。还要注意的是，相遇只发生在Kaf和其他学生之间，其他两个学生之间不会发生相遇(一个单元格里可能有多个学生)。

你的目标

你要帮助Kaf找到教室入口。为此，你必须指挥Kaf进行一系列的移动，最后进行最后一种移动。不过，在你指挥Kaf采取任何移动之前，你要在你的QQ空间上发布这一系列移动顺序。然后，你必须要按照这一连串的移动走下去。

其他学生的目标

由于你在QQ空间中发布了移动顺序，其他学生甚至在你第一次移动之前就会知道你的准确动向。如果可能的话，他们都会尽可能保证与Kaf有一次相遇。无法与Kaf相遇的学生将什么也不做。

你的任务

打印你指挥Kaf必须与其他学生相遇的最少次数，假定你选择了能最小化这一次数的移动顺序。请注意，您不必尽量减少移动次数。

输入格式

第一行由两个整数组成： $r$ 和 $c$ $( 1 \leq r,c \leq 1000 )$，表示教学楼的行数和列数。接下来的 $r$ 行将分别描述教学楼的一行，其中每个字符代表一个单元格的内容：

• '#'：墙所在的单元格。
• 'S'：空单元格，也是您的起始位置。这种情况在地图中只会出现一次。
• 'E'：一个空单元格，也是教室入口所在的位置。地图中将正好出现一次。
• 一个数字 $(0 - 9)$ ：由数字 $X$ 代表的单元格表示该单元格是空的，并有 $X$ 个学生在这个格子上(特别的，如果 $X$ 为 $0$，则表示该单元格上没有学生)。

保证您你指挥Kaf可以通过一连串的移动从起始位置到达教教室入口。

输出格式

输出一行表示如果你选择的策略能最小化这个数字，那么Kaf必须相遇的最少次数。

样例 #1

5 7
000E0#3
#0##0#0
010#0#0
2#0#0#0
0#0S000

3

样例 #2

1 4
SE23

2