The Agency

You are building an interplanetary travel service, and your first task is to find the cheapest way to travel between two planets. Conveniently, the planets and the flights between them have a special structure. Each planet is represented by a string of N bits. There is a direct flight between two planets exactly when their N-bit strings differ in exactly one position (that is, exactly one bit is flipped).

The cost of a flight is the cost of landing on the destination planet. Each bit position i has an associated tax. To land on a planet you must pay the i-th tax for every position i whose bit is 1, so the cost of landing on a planet is the sum of these applicable taxes. You do not pay anything to start on the starting planet; you only pay to land on each planet you fly to.

Given the starting planet, the ending planet, and the cost of each tax, compute the minimum total cost of a sequence of flights that takes you from the starting planet to the ending planet.

The input contains several test cases. Each test case consists of two lines. The first line contains N (1 ≤ N ≤ 1000), the number of bits representing a planet; S, a string of N zeros and ones giving the starting planet; and E, a string of N zeros and ones giving the ending planet. The second line contains N integers, the i-th of which is the cost of the i-th tax (bit positions are numbered from 1). Every tax is between 1 and 1,000,000. A line containing a single 0 terminates the input.

For each test case, output a single line Case k: c, where k is the test-case number (starting at 1) and c is the minimum total cost to travel from the starting planet to the ending planet.