Winter's Coming

″You are too young to be burdened with all my cares,″ the father told her, ″but you are also a Stark of Winterfell. You know our words.″
″Winter is coming,″ Arya whispered, thinking of Nymeria. She hugged her knees against her chest, suddenly afraid.
″Remember the sigil of our House, Arya. Let me tell you something about it. When the snows fall and the white winds blow, the lone Wolf dies, but the pack survives. Summer is the time for squabbles. In winter, we must protect one another, keep each other warm, share our strengths. So if you must hate, Arya, hate those who would truly do us harm. Sansa... Sansa is your sister. You may be as different as the sun and the moon, but the same blood flows through both your hearts. You need her, as she needs you... and I need both of you, gods help me. Gods commanded us to build a long wall, which is regardless of the thickness, to defend the attack from the Lannister. Now we should carry out the wall.″ Ned Stark sounded so tired that it made Arya sad.
″I do not mean to frighten you, but neither will I lie to you. We have come to a dark dangerous place, child. We have enemies who mean us ill in the King's Landing. We'll point the swords to the Lannister, rather than fight a war among ourselves. Our construction crew will build a wall which connect the north border and south border, separate the mainland into exact two parts. All our Wolf's cities should lie on the left part, while All Lannister's cities lie on the right part. Precisely, the wall can't pass through a grid more than once, and should run parallel or vertically to the four borders. With winter soon upon us, that is a different matter that we should minimize the time cost.″
″How much time do we have, roughly?″ Arya take out the draft and has been ready to calculate.
″Winter is coming.″ Her father frowned.

There are multiple cases. The first line of each case contains two integers, N, M (1 ≤ N ≤ 20, 1 ≤ M ≤ 10), indicating the width and length of the mainland's layout.
In the map, the character is 'W' indicated the Wolf's city, 'L' indicated the Lannister's city, '#' means a grid where forbade any construction, and a number in '0'-'9' indicated the time cost to build a wall on this grid.

For each case, output one integer, the minimum time cost to build a valid wall, or -1 if we can't work out an approach.

6 8
88W888L8
888#W888
888888L8
8W88L#88
8888888L
88888W88

88

2013 Asia Changsha Regional Contest