题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

釜山广域市为了方便游客的交通出行，销售以下几种交通票券。

类别	使用人数	有效期	价格	备注
1 日票	1 人	购买当天，共 1 天	$p_1$	有效期内仅限购买者本人使用
3 日票		含购买当天在内的连续 3 天	$p_3$
5 日票		含购买当天在内的连续 5 天	$p_5$
组合票	2 人	含购买当天在内的连续 4 天	$p_{pair}$	有效期内两人均可使用

所有票券均在购买后立即生效，并可在票券上标明的有效期内使用交通工具。当然，即使持有票券但未使用交通工具，或持有多张有效期重叠的票券，或票券的有效期超出了 N 天的观光行程也都是允许的。另外请注意，$p_1 \le p_3 \le p_5$ 这一关系并非总是成立。

Hankook 和 Jeong-ul 将在釜山一同停留 $N$ 天。但是，两人各自制定了自己的观光计划，并决定了每天自己是否要进行观光。为了完成观光行程，对于每个人，在他们进行观光的每一天，都必须持有一张有效的票券（包括组合票）。

例如，假设 $N=9$，$p_1=3, p_3=7, p_5=12, p_{pair}=15$，Hankook 和 Jeong-ul 各自的日程如下：

日期	1	2	3	4	5	6	7	8	9
Hankook	X	O	O	X	O	O		X	O
Jeong-ul	O		X		X			O	X

(O 代表观光，X 代表不观光)

如果只使用 1 日票，总观光天数为 11 天 (Hankook 6 天 + Jeong-ul 5 天)，费用为 11 (观光天数) × 3 (1 日票价格) = 33。

但是，如果两人在第 5 天至第 8 天共享一张组合票，总费用仅为 30。

更有甚者，如果 Hankook 购买一张第 5 天至第 7 天的 3 日票，Jeong-ul 购买一张第 6 天至第 8 天的 3 日票，总费用可以节省至 29。

当 Hankook 的日程由字符串 $A = A_1A_2\cdots A_N$ 表示，Jeong-ul 的日程由字符串 $B = B_1B_2\cdots B_N$ 表示时，对于日期 $i(1 \le i \le N)$:

• 如果 Hankook 进行观光，$A_i=1$；否则 $A_i=0$
• 如果 Jeong-ul 进行观光，$B_i=1$；否则 $B_i=0$

请根据以上形式给出的日程，编写一个程序，计算出为了确保在每个人进行观光的每一天都持有至少一张有效票券（包括组合票）所需的最少费用。

输入格式

第一行给定一个表示在釜山停留时间的整数 $N$。

第二行给定一个表示 Hankook 日程的字符串 $A$。

第三行给定一个表示 Jeong-ul 日程的字符串 $B$。

第四行给定 $p_1, p_3, p_5, p_{pair}$，以空格分隔。

输出格式

在第一行输出表示最小费用的整数。

9
011011101
110001110
3 7 12 15

29

9
011011101
110001110
1 10000 10000 10000

11

提示

限制条件

• 给定的所有数都是整数。
• $1 \le N \le 2000$。
• 字符串 $A, B$ 的长度均为 $N$，且所有字符均为 0 或 1。
• $1 \le p_1, p_3, p_5, p_{pair} \le 10000$。

子任务

1. (6 分) $p_1 = 1$，$p_3 = p_5 = p_{pair} = 10000$。
2. (12 分) $p_{pair} = 1$，$p_1 = p_3 = p_5 = 10000$。
3. (16 分) 对于所有 $i(1 \le i \le N)$，都有 $A_i = B_i = 1$。
4. (24 分) 对于所有 $i(1 \le i \le N)$，都有 $B_i = 0$。
5. (42 分) 无附加限制条件。