Description

Xiaoming loves playing the matchstick game: first he uses matchsticks to form an equation that may be incorrect, then by adding, deleting, or moving matchsticks, he makes the equation correct. The following image shows what each digit looks like:

We only consider expressions of the form "A = B", where A and B are two integers with the same number of digits.

Xiaoming can perform three types of operations:

1. Add one matchstick at any position.
2. Delete one matchstick from any position.
3. Move any one matchstick to another position.

After all operations, both sides of the equal sign must be valid numbers and exactly the same. We agree on the following rules:

1. Xiaoming cannot eliminate any digit entirely. That is, you may delete some sticks from a digit, but you must not make that digit disappear.
2. Xiaoming cannot create any new digit. That is, you may add sticks onto an existing digit or move sticks onto an existing digit, but you must not create a new digit out of nothing.
3. Xiaoming cannot split or merge digits. For example, turning an 8 into two 1s, or merging two 1s into one 8, is not allowed.
4. The matchstick representing the digit 1 must be placed on the right side; placing it on the left does not form a valid digit.

Each operation has a certain cost:

• For an add operation, if this is the $i$-th add, the cost of this step is $p_1\times i+q_1$.
• For a delete operation, if this is the $i$-th delete, the cost of this step is $p_2\times i+q_2$.
• For a move operation, if this is the $i$-th move, the cost of this step is $p_3\times i+q_3$.

For example, if Xiaoming adds 3 matchsticks, moves 1 matchstick, and deletes 2 matchsticks, then his total cost is $[(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)]$.

Xiaoming wants to know the minimum cost to make the equation correct. Can you write a program to help him?

Input Format

• Line 1: An integer L, the number of digits on each side of the equation.
• Lines 2–3: Each line contains a length L string consisting only of digits, representing the numbers on the two sides of the equation.
• Line 4: Six non-negative integers not exceeding 100: $p_1,q_1,p_2,q_2,p_3,q_3$.

Output Format

Output one line containing a single integer: the minimum total operation cost to make the equation correct.

2
46
78
0 1 0 1 0 1

2

2
23
52
1 1 1 1 1 1

9

Hint

For 30% of the testdata, $L\le 20$, and $p_1 = p_2 = p_3 = 0$.

For 60% of the testdata, $L\le 100$.

For 100% of the testdata, $L\le 200$.

Translated by ChatGPT 5