Containers
By Maratona de Programação da SBC – 2016 
Brazil
By Maratona de Programação da SBC – 2016 Brazil
The SBC-System Containers Balancing needs to be updated to work with a new class of ships, the "two by four", which are ships that can carry eight large containers in an arrangement of two rows and four columns, as shown in the figure to side. These ships have a fixed crane which is capable of producing a single type of movement: up two adjacent containers in the row or column, and exchange them position. To speed up the loading ports, eight containers are shipped in any one of eight positions, defining an initial configuration. After the ship leaves the port, the crane must move the containers to make them a final default setting for the trip.
The problem is that the fuel cost for the crane perform a movement equals the sum of the weights of two adjacent containers whose positions have been changed. Given the weight of the containers in each position in the initial and final configurations, the SBC must compute the minimum possible total cost of a sequence of movements which takes the containers from initial configuration to the final configuration.
The entry consists of four rows, each containing four integers between 1 and 1000, inclusive. The first two lines define the weights in the initial configuration and the last two lines, the weights in the final configuration. There is always a solution, because the containers in the initial and final configurations are the same, with possibly changed positions.
Your program should produce a single line containing an integer, representing the minimum total cost of a sequence of movements that take the initial configuration to the final configuration.
| Input Samples | Output Samples |
|
3 1 2 1 |
81 |
|
1 2 3 4 |
50 |
|
34 5 6 998 4 17 77 84 34 5 6 998 4 17 77 84 |
0 |