Cliff Climbing

At 17:00, special agent Jack begins his escape from the enemy camp. Between the camp and the nearest safety zone stands an almost vertical cliff. Jack must climb this cliff by stepping his feet on the blocks that cover it. Some blocks are slippery, so it takes extra time to place a foot on them safely; other blocks are too loose to bear his weight and must be avoided. Write a program that computes the minimum time needed to finish the climb.

The cliff is covered with square blocks. Jack starts from the ground below the cliff by stepping his left or right foot onto one of the blocks marked 'S' in the bottom row. The number written on a block is its "slippery level": it takes $t$ time units ($1 \le t \le 9$) to place a foot safely on a block marked $t$. He cannot step on a block marked 'X'. He finishes the climb as soon as either foot reaches one of the blocks marked 'T' in the top row.

Jack's movement must satisfy the following rules. After placing his left (or right) foot on a block, he may only move his right (or left) foot next; that is, his feet move alternately. His left-foot position $(l_x, l_y)$ and right-foot position $(r_x, r_y)$ must always satisfy $l_x < r_x$ and $|l_x - r_x| + |l_y - r_y| \le 3$. Thus, once the left foot is fixed, the right foot must be placed on one of the nine blocks that satisfy this condition; likewise, once the right foot is fixed, the left foot must be placed on one of the nine blocks that satisfy it.

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space (0 0). Each dataset has the following format:

w h
s(1,1) ... s(1,w)
s(2,1) ... s(2,w)
...
s(h,1) ... s(h,w)

The integers $w$ and $h$ are the width and height of the cliff's block matrix, where $2 \le w \le 30$ and $5 \le h \le 60$. Each of the following $h$ lines consists of $w$ characters separated by single spaces. The character $s(y, x)$ describes the block at position $(x, y)$ as follows:

• 'S': Jack may start climbing from this block.
• 'T': the climb finishes when a foot reaches this block.
• 'X': a foot cannot be placed on this block.
• '1'–'9' ($= t$): it takes $t$ time units to place either foot on this block.

Assume that placing a foot on a block marked 'S' or 'T' takes no time.

For each dataset, print a single line containing one decimal integer: the minimum time required to finish the climb. If the climb cannot be completed, print a single line containing "-1" instead. Each line must contain no characters other than these digits.