G. Great Wall of China

Time Limit: 6 sec

Description

The alfalfas team is visiting the Great Wall of China. They want to cross it from beginning to the end, but some parts of the Great Wall was rebuilt for the tourists and it is necessary to pay a toll. Then, they bought a map that represented the Great Wall as a grid of 5 rows and n columns. Each site was marked with a digit that represents the cost to the toll. The alfalfas want that you write a program to get the way to cross the Great Wall from column 0 to n - 1 with the minimum cost. They began in the first column, each per represented by '@'. The cost of all sites in the first column are 0.They can move only horizontally and vertically. They want to visit all unique parts of the Great wall, so they never pass through the sites that another alfalfa has visited.

The Input

For each test case the first line contain an integer n (3 ≤ n ≤ 1000). In the follow 5 lines contain n characters, each character would be indicate the toll of this site and in the first columns the characters would be 0, or '@' that indicate the position of an alfalfa, there must be always be three '@'.

The Output

For each test case you must print the minimum price that the alfalfas need to pay for their travel.

27
@00100000000000102000000000
@00100000000000102111000000
000010000000011002110000000
@00011110000100002111000000
000000000011100002000000000
3
@10
@00
@00
000
000
12
024841026058
@03990540049
@01108404608
030789005500
@95750159143
0

13
1
101

Problemsetter: Rodrigo Burgos Domínguez