부산 관광

문제

부산광역시는 관광객의 교통 이용 편의를 위하여 다음 네 종류의 교통 티켓을 판매한다.

구분	사용 인원	유효 기간	가격	비고
1일권	$11$ 명	구매한 날 당일 1일	$p_{1}p\_1$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
3일권	$11$ 명	구매한 날을 포함한 연속 3일	$p_{3}p\_3$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
5일권	$11$ 명	구매한 날을 포함한 연속 5일	$p_{5}p\_5$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
묶음권	$22$ 명	구매한 날을 포함한 연속 4일	$p_{\text{pair}}p\_\{\backslash text\{pair\}\}$	유효 기간 내에 두 사람 모두 교통 이용 가능

모든 티켓은 구매 즉시 효력이 발생하며, 표에 명시된 기간 동안 매일 교통을 이용할 수 있다. 물론, 티켓을 보유하고 있는 채로 교통을 이용하지 않아도 되고, 유효한 티켓을 동시에 여러 장 보유해도 되고, 티켓의 유효 기간이 $NN$일간의 관광 일정 이후에 끝나도 무방하다. 그리고 p_1 ≤ p_3 ≤ p_5가 항상 성립하는 것은 아님에 유의하라.

한국이와 정올이는 부산에서 $NN$일간 같이 머무른다. 하지만, 둘은 각각 자신만의 관광 일정을 세워두어 각 날마다 자신이 관광을 진행할지의 여부를 결정해 두었다. 관광 일정을 소화하기 위해서는 두 사람 모두 관광을 진행하는 날마다 적어도 한 장의 유효한 티켓(묶음권 포함)을 보유해야 한다.

---

예를 들어, $N=9N\; =\; 9$이고, $p_1=3p\_1\; =\; 3$, $p_3=7p\_3\; =\; 7$, $p_5=12p\_5\; =\; 12$, $p_{\text{pair}}=15p\_\{\backslash text\{pair\}\}\; =\; 15$이고, 한국이와 정올이 각각의 일정이 아래와 같은 경우를 고려해 보자.

날짜	$11$	$22$	$33$	$44$	$55$	$66$	$77$	$88$	$99$
한국	X	O	O	X	O	O	O	X	O
정올	O	O	X	X	X	O	O	O	X

1일권만 사용하면 총 $1111$(관광 일수) $\times \backslash times$ $33$ (1일권 가격) $=33=\; 33$의 비용이 든다.

하지만, 만약 두 사람이 5일차-8일차 동안 묶음권 $11$장을 공유하면 총 $3030$의 비용만 소모된다.

심지어 한국이가 5일차-7일차, 정올이는 6일차-8일차를 각각 3일권으로 구입하면 총 비용이 $2929$로 더 절약된다.

한국이의 일정을 나타내는 문자열 $A=A_1{A}_2\cdots A_{N}A\; =\; A\_1\; A\_2\; \backslash cdots\; A\_N$와 정올이의 일정을 나타내는 문자열 $B=B_1{B}_2\cdots B_{N}B\; =\; B\_1\; B\_2\; \backslash cdots\; B\_N$가 날짜 $ii$ (1 ≤ i ≤ N)에 대해

• 한국이가 관광을 진행하면 $A_i=1A\_i\; =\; 1$, 아니면 $A_i=0A\_i\; =\; 0$
• 정올이가 관광을 진행하면 $B_i=1B\_i\; =\; 1$, 아니면 $B_i=0B\_i\; =\; 0$

의 형태로 주어질 때, 두 사람 모두 관광을 진행하는 날마다 적어도 한 장의 유효한 교통 티켓(묶음권 포함)을 보유하도록 하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하라.

입력

첫 번째 줄에 부산에 머무르는 기간을 나타내는 정수 $NN$이 주어진다.

두 번째 줄에 한국이의 관광 일정을 나타내는 문자열 $AA$가 주어진다.

세 번째 줄에 정올이의 관광 일정을 나타내는 문자열 $BB$가 주어진다.

네 번째 줄에 $p_1,p_3,p_5,p_{\text{pair}}p\_1\; ,\; p\_3\; ,\; p\_5\; ,\; p\_\{\backslash text\{pair\}\}$가 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에 최소 비용을 나타내는 정수를 출력한다.

9
011011101
110001110
3 7 12 15

29

9
011011101
110001110
1 10000 10000 10000

11