Planks

Build a bridge across a swamp by connecting tree stumps with planks.

You are fleeing across a crocodile-infested swamp. The stumps in the swamp sit on a regular 10×10 grid, with neighbouring grid points 1 foot apart. There is a stump on solid land at the upper-left corner, position (1, 1), and another on the far bank at the lower-right corner, position (10, 10). Nearby you also have a pile of planks.

Each plank has a fixed length. A plank may be laid down to connect two stumps that lie in the same row or the same column and are exactly the plank's length apart (measured in feet). Planks may only be placed horizontally or vertically — never diagonally — and each plank may be used at most once. A plank may pass over stumps that lie between its two ends, and planks are allowed to cross one another.

Starting at stump (1, 1), you cross by stepping from stump to stump along the planks you lay, and you want to reach stump (10, 10). Cross using as few planks as possible.

The first 10 lines describe the swamp as a 10×10 grid of characters. A period (.) is open water and an asterisk (*) is a stump. The stumps at (1, 1) and (10, 10) are always present. Here (r, c) denotes row r from the top and column c from the left, both counted from 1.

Each following line describes one independent set of planks (there may be several sets, and they all share the same swamp). On such a line the first integer is the number of planks available (at most 20), and the remaining integers are the lengths of those planks.

For each plank set, print one line.

If you can reach stump (10, 10) starting from stump (1, 1), print the minimum number of planks needed to make the crossing. Otherwise print no solution possible.

Print the results in the same order as the plank sets, one result per line, with no blank lines between them.