In the futuristic city of Numetropolis, digital codes govern all forms of communication. You’ve been tasked with designing a special digital sequence of N digits for the city’s central computer.
The sequence must be constructed using only the digits 2, 4, 6, or 8, but there’s a catch - no two adjacent digits can be the same, and each digit comes with a specific cost for being placed in any position.
The costs are given in a matrix where each row corresponds to a position in the string, and each column represents the cost of placing a specific digit.
Your mission is to design this sequence with the lowest possible construction cost, while ensuring no adjacent digits are identical.
Can you find the minimum cost to complete this crucial digital string for Numetropolis?
The second line of the input contains a single integer N, representing the size of the array cost.
Next n lines contain four space-separated integers representing the cost of adding 2, 4, 6 and 8 to the ith position.
1
2
2 3 4 5
7 4 3 1
Sample Output
3
Explanation
The best choice is to fill 1st space with the digit "2" with cost 2 and the 2nd space with the digit "8" with cost 1. so the total cost will be 3 and the final digital string will be "28".