bee 1972 - Nemesis

Nemesis, the goddess of revenge, has raged against Euterpe, the Muse of delight, and has put her in a maze infested by beasts. Now, only Hercules can save Euterpe. Starting his journey at somewhere in the maze, Hercules can only advance to a maze position guarded by a best if he kills the beast. Though terrible, a beast can never leave the position it guards. Furthermore, different beasts may require from Hercules different amounts of energy in order to be killed. Help Hercules to save Euterpe spending the minimum of energy as possible, knowing that he can move only in vertical and horizontal directions and, despite of being an invincible hero and having infinite energy, Hercules cannot destroy the walls of the maze.

Input

The first input line consist of two integers, N and M (2 ≤ N, M ≤ 500), which represent the number of lines and the number of columns in the maze. The next N lines describe the maze and have exactly M characters each, which can be:

H, if that is the position where Hercules starts his journey;
E, if that is the position where Euterpe is arrested;
., if that position is a free position;
#, if that position is a wall;
an integer X between 1 and 9, if that position is guarded by a best that requires X of Herculean energy in order to be killed.

Output

Print a line containing singly the minimum amount of energy needed for Hercules to get to Euterpe. If it is not possible for Hercules to get to Euterpe, print a line containing singly the word ARTSKJID.

Input Samples	Output Samples
3 10 .138764..2 7H###19##2 .23#61.E#2	27

2 2 E# #H	ARTSKJID

2 2 H2 2E	2