3166 -- Jumping Frog

Language:

Jumping Frog

Time Limit: 1000MS		Memory Limit: 131072K
Total Submissions: 505		Accepted: 129

Description

A rivulet is situated in the heartland of Byterland. For centuries it was renowned for its beauty but the beauty is now gone. During the recent years, an increasing number of people have built their villas by the riverside and kept dumping garbage into the rivulet. This evening a little frog loses himself on the river when he is hurrying home.

The figure above shows why the frog gets lost. Seen from above, garbage dumped into the river sticks together and become beam-shaped blocks that extend from the mid-axis (x-axis in the figure) of the rivulet till they reach one of the banks. The garbage blocks alternate in touching the two banks and the leftmost block always touches the bank shown at the bottom. The blocks are always located at integral coordinates and they divide the rivulet into several segments of possibly different lengths. As in the figure above, there are three segments of lengths 2, 5 and 3 in order. At each integral abscissa strictly inside a segment (not on the border), there is a lotus leaf located at some ordinate. The ordinates are also integral.

The little frog is going home by jumping from one leaf to another. At first it is standing on the leftmost leaf and its home is where the rightmost leaf lies. The frog jumps straight and it cannot jump higher than the garbage blocks. If the trajectory of its jump touches any garbage, it will get stuck in and have little chance to get out.

Please calculate the minimal distance the frog has to jump before arriving at home or determine that it is impossible to go home. Sizes of the frog and the leaves and thickness of the garbage blocks are negligible in your calculation.

Input

For n segments divided into by n − 1 garbage blocks, you will be given n strings with the information of the coordinates of each lotus leaf. The i-th string is for the i-th segment from the left and if it is l_i characters long, that means the corresponding segment has length l_i + 1. The characters in a string describe the leaves in a segment from left to right. A character is one of A…Z and b…z, indicating an ordinate of 0…25 and −1…−25 respectively.

Each test case starts with n (1 ≤ n ≤ 50) on the first line. The next n lines each contain a non-empty string with no more than 50 characters.

This is a multiple test cases problem. Test cases are followed by blank lines. Please process to the end of the input.

Output

For each test case, output a single line with a real number representing the minimal distance (rounded up to 4 digits after the decimal point) the frog has to jump from the leftmost leaf to the rightmost one. Output −1 if the poor frog can never get home.

Sample Input

3
b
CCbB
bA

3
bbb
bB
b

2
B
b

3
O
K
q

Sample Output

Hint

Explanation for the sample test cases:

For the first case: This case follows the figure above.
For the second case: Sometimes the little frog needs to jump from right to left.
For the fourth case: The frog can jump directly from the first to the last leaf.

Source

POJ Monthly--2006.12.31, Zhu, Zeyuan