부산 관광 timer 2s memory 1024MB

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

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

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

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

1일권만 사용하면 총 11(관광 일수) x 3 (1일권 가격) = 33의 비용이 든다.

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

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

한국이의 일정을 나타내는 문자열 A = A_1A_2 \cdots A_N와 정올이의 일정을 나타내는 문자열 B = B_1B_2 \cdots B_N가 날짜 i(1 \le i \le N)에 대해

• 한국이가 관광을 진행하면 A_i = 1, 아니면 A_i = 0

• 정올이가 관광을 진행하면 B_i = 1, 아니면 B_i = 0

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

[제약 조건]

• 주어지는 모든 수는 정수이다.

• 1 \le N \le 2\,000

• 문자열 A, B의 길이는 각각 N이며 모든 문자는 0또는 1이다.

• 1 \le p_1,p_3,p_5,p_{pair} \le 10\,000