Problem Background

SHOI2012D1T1

Problem Description

Xiao Ming loves playing the matchstick game: first, he arranges matchsticks to form a possibly incorrect equation, and then he adds, removes, or moves matchsticks to make the equation correct. The figure below shows the appearance of each digit:

We only consider equations of the form "A = B", where A and B are 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, both sides of the equation must be valid numbers and exactly equal. We stipulate:

1. Xiao Ming cannot eliminate any digit, meaning he can remove part of a digit's matchsticks but cannot make it disappear;
2. Xiao Ming cannot add any digit, meaning he can add matchsticks to an existing digit or move matchsticks to an existing digit, but cannot create a new digit out of nothing;
3. Xiao Ming cannot split or merge digits, such as turning an 8 into two 1s, or merging two 1s into an 8;
4. The matchstick representing 1 must be placed on the right side, and placing it on the left is not a valid digit. Each operation has a certain cost:
   - For an add operation, if it is the $i$-th add operation, the cost is $p_1 \times i + q_1$;
   - For a remove operation, if it is the $i$-th remove operation, the cost is $p_2 \times i + q_2$;
   - For a move operation, if it is the $i$-th move operation, the cost is $p_3 \times i + q_3$.

For example, if Xiao Ming adds 3 matchsticks, moves 1 matchstick, and removes 2 matchsticks, his total cost would be $[(p_1 \times 1 + q_1) + (p_1 \times 2 + q_1) + (p_1 \times 3 + q_1)] + (p_3 \times 1 + q_3) + [(p_2 \times 1 + q_2) + (p_2 \times 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 Format

The first line contains an integer L, representing the number of digits in both numbers of 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 contains six non-negative integers not exceeding 100: $p_1, q_1, p_2, q_2, p_3, q_3$.

Output Format

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

Sample Input and Output

Sample Input #1

2
46
78
0 1 0 1 0 1

Sample Output #1

2

Sample Input #2

2
23
52
1 1 1 1 1 1

Sample Output #2

9

Notes

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$.

见题面 Input 部分

见题面 Output 部分