Problem U
Bitmask
Masking greatly reduces the transmission of certain viruses. This is true for computer viruses as well. In order to protect binary data from infection, we must cover it up with masks!
Binary data can be represented as a string of $n$ $0$s and $1$s. A bitmask can be used to cover a portion of the data. Specifically, a bitmask of length $m \leq n$ can be used to cover $m$ consecutive bits in the data. To maximize protection, only well-fitting masks can be used. That is, each covered bit in the binary data is the opposite to the corresponding bit in the mask. For example, if the data is
\[ 1001\ 0110\ 1010 \]then the mask $011$ can be used to cover positions $1$–$3$. The mask $101$ can be used to cover positions $3$–$5$ and $10$–$12$.
The cost to produce a bitmask of length $i$ is $C_ i$. Fortunately, if you have already produced a particular bitmask, you can make as many copies as you wish for free! Thus, one can produce two masks of 101 for only $C_3$.
What is the minimum cost to cover a particular piece of binary data with bitmasks? Every bit in the data must be covered by exactly one bitmask.
Input
The first line of input consists of a string of $0$s and $1$s representing the binary data. The length of the string $n$ satisfies $1 \leq n \leq 12$. The second line of input consists of $n$ integers $C_1, \ldots , C_ n$, where $1 \leq C_ i \leq 100$.
Output
Output the minimum cost to produce the bitmasks to cover the binary data.
| Sample Input 1 | Sample Output 1 |
|---|---|
10101010 2 3 7 1 4 3 8 9 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
101010101111 26 51 24 79 15 46 22 79 47 84 60 100 |
37 |
