The Agency#2675
Following in the footsteps of a number of flight search startups, you want to create the first interplanetary travel website. Your first problem is to quickly find the cheapest way to travel between two planets. You have an advantage over your competitors because you have realized that all the planets and the flights between them have a special structure. Each planet is represented by a string of bits, and there is a flight between two planets if their -bit strings differ in exactly one position.
The cost of a flight is the cost of landing on the destination planet. If the -th character in a planet's string is a , then the -th tax must be paid to land. The landing cost on a planet is the sum of all applicable taxes.
Given the starting planet, ending planet, and the cost of each -th tax, determine the cheapest set of flights to get from the starting planet to the ending planet.
Input for each test case consists of two lines. The first line contains (1 \leq N \leq 1000), the number of bits representing a planet; , a string of zeros and ones representing the starting planet; and , a string of zeros and ones representing the ending planet. The second line contains integers, where the -th integer is the cost of the -th tax. All costs are between and . The input is terminated by a line consisting of a single .
For each test case, output one number—the minimum cost to get from the starting planet to the ending planet, using the format shown below.
Example 1