Binary Transformations

Time limit1sMemory limit256 MB

Summary

Given starting bits, target bits, and per-bit costs, flipping a bit i costs the sum of costs of all bits equal to 1 after the flip; find the minimum total price to reach the target.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

There are $n$ bits numbered from $1$ to $n$ . Bit $i$ starts with the value $a_i$ , which is $0$ or $1$ , and its cost is $c_i$ .

One operation picks a bit $i$ and flips its value, so $0$ becomes $1$ and $1$ becomes $0$ . The price of that operation is the sum of $c_j$ over every bit $j$ whose value is $1$ after the flip. When bit $i$ itself turns into $1$ , its own cost $c_i$ is part of that sum.

You may apply the operation to any bit, any number of times, in any order. Find the smallest total price that makes bit $i$ hold the value $b_i$ for every $i$ .

Input

The first line contains the integer $n$ ( $1 \le n \le 5\,000$ ), the number of bits.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ( $1 \le c_i \le 10^9$ ), the cost of each bit.

The third line contains a string of $n$ characters $a_1 a_2 \dots a_n$ , the starting values.

The fourth line contains a string of $n$ characters $b_1 b_2 \dots b_n$ , the required values.

Output

Print the smallest total price on one line.

Examples2

Example 1
Input
```
5
5 2 6 1 5
01110
10011
```
Expected output
```
21
```
Example 2
Input
```
6
100 1 1 1 1 1
111000
100111
```
Expected output
```
112
```