Matchstick Game

Xiao Ming loves playing a matchstick game: he first arranges matchsticks to form a potentially incorrect equation, then makes the equation correct by adding, removing, or moving matchsticks. The figure below shows the appearance of each digit:

We only consider equations of the form "A = B", where A and B are two integers with the same number of digits. Xiao Ming can perform three types of operations: 1. Add a matchstick at any position; 2. Remove a matchstick from any position; 3. Move a matchstick to another position.

After all operations are completed, both sides of the equal sign must be valid numbers and must be exactly equal. We stipulate: 1. Xiao Ming cannot eliminate any digit; that is, he can remove some matchsticks from a digit, but he cannot make the digit disappear; 2. Xiao Ming cannot add any new digits; that is, he can add matchsticks to an existing digit or move matchsticks to an existing digit, but he cannot create a new digit out of thin air; 3. Xiao Ming cannot split or merge digits; for example, he cannot turn an 8 into two 1s, or merge two 1s into an 8; 4. The matchstick representing 1 must be placed on the right side; placing it on the left is not a valid digit.

Each operation has a certain cost: For an addition operation, if it is the $i$-th addition operation performed, the cost of this step is $p_1 \cdot i + q_1$. For a removal operation, if it is the $i$-th removal operation performed, the cost of this step is $p_2 \cdot i + q_2$. * For a move operation, if it is the $i$-th move operation performed, the cost of this step is $p_3 \cdot i + q_3$.

For example, if Xiao Ming adds 3 matchsticks, moves 1 matchstick, and removes 2 matchsticks in the game, his total cost is $[(p_1 \cdot 1 + q_1) + (p_1 \cdot 2 + q_1) + (p_1 \cdot 3 + q_1)] + (p_3 \cdot 1 + q_3) + [(p_2 \cdot 1 + q_2) + (p_2 \cdot 2 + q_2)]$.

Xiao Ming wants to know how to make the equation correct with the minimum cost. Can you write a program to help him?

Input

The first line contains an integer $L$, representing the number of digits of the two numbers in the equation. The second and third lines each contain a string of length $L$ consisting only of digits, representing the numbers on both sides of the equation. The fourth line provides six non-negative integers $p_1, q_1, p_2, q_2, p_3, q_3$, all of which are no greater than 100.

Output

Output a single line containing an integer, which is the minimum operation cost to make the equation correct.

Examples

Input 1

2
46
78
0 1 0 1 0 1

Output 1

2

Input 2

2
23
52
1 1 1 1 1 1

Output 2

2

Constraints

For 30% of the data, $L \le 20$ and $p_1 = p_2 = p_3 = 0$; For 60% of the data, $L \le 100$; For 100% of the data, $L \le 200$.