시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB68382857.143%

문제

$0$과 $1$로만 구성된 두 문자열 $s_1$, $s_2$가 있다. 두 문자열의 길이는 $N$으로 같다.

이제 다음 두 가지 연산을 $0$회 이상 반복해 두 문자열의 모든 문자를 $1$로 만들려고 한다. 각 연산을 한 번 하는 데 소모되는 비용은 각각 $c_1$, $c_2$이다.

  1. $1$ 이상 $N$ 이하의 정수 $a$를 선택하여, 두 문자열 $s_1$, $s_2$ 중 한 문자열의 $1$번째 문자부터 $a$번째 문자까지 동시에 반전한다.
  2. $1$ 이상 $N$ 이하의 정수 $b$를 선택하여, 두 문자열 $s_1$, $s_2$의 $b$번째 문자를 동시에 반전한다.

문자열 $S$의 $i$번째 문자를 반전하는 연산은 $S$의 $i$번째 문자가 $1$이라면 $0$으로 만들고, $0$이라면 $1$로 만드는 연산이다.

또한 문자열 $S$의 $L$번째 문자부터 $R$번째 문자까지 동시에 반전하는 연산은 $L\le i\le R$을 만족하는 모든 정수 $i$에 대해 동시에 문자열 $S$의 $i$번째 문자를 반전하는 연산이다.

$s_1$, $s_2$의 모든 문자를 $1$로 만드는 데 필요한 최소 비용을 구해 보자.

입력

첫째 줄에 문자열 $s_1$과 $s_2$의 길이 $N$이 주어진다. $(1\le N\le 100\, 000)$

둘째 줄에 문자열 $s_1$이 주어진다.

셋째 줄에 문자열 $s_2$가 주어진다.

넷째 줄에 두 정수 $c_1$, $c_2$가 공백으로 구분되어 주어진다. $(1\le c_1, c_2 \le 10^9)$

출력

$s_1$, $s_2$의 모든 문자를 $1$로 만드는 데 필요한 최소 비용을 출력한다.

예제 입력 1

5
00100
00011
10 1

예제 출력 1

21

다음과 같이 연산하는 경우, 소모되는 총 비용을 $21$로 하여 $s_1$, $s_2$ 의 모든 문자를 $1$로 만들 수 있다. 각 연산 수행 직후 바뀐 문자는 빨간색으로 표시한다.

$1$번째 연산: $s_1$의 $1$번째 문자부터 $5$번째 문자까지 반전한다. 이 때 소모되는 비용은 $10$이다.

$1$번째 연산을 수행한 결과는 아래와 같다.

$s_1$ $1$ $1$ $0$ $1$ $1$
$s_2$ $0$ $0$ $0$ $1$ $1$

$2$번째 연산: $s_2$의 $1$번째 문자부터 $2$번째 문자까지 반전한다. 이 때 소모되는 비용은 $10$이다.

$2$번째 연산을 수행한 결과는 아래와 같다.

$s_1$ $1$ $1$ $0$ $1$ $1$
$s_2$ $1$ $1$ $0$ $1$ $1$

$3$번째 연산: $s_1$과 $s_2$의 $3$번째 문자를 반전한다. 이 때 소모되는 비용은 $1$이다.

$3$번째 연산을 수행한 결과는 아래와 같다.

$s_1$ $1$ $1$ $1$ $1$ $1$
$s_2$ $1$ $1$ $1$ $1$ $1$

이 방법으로 연산하는 경우, 모든 문자를 $1$로 바꾸기까지 소모되는 총 비용은 $10 + 10 + 1 = 21$이다.

이보다 소모되는 비용을 더 적게 하여 모든 문자를 $1$로 만들 수 없음이 보장된다.

예제 입력 2

5
00100
00011
1 10

예제 출력 2

4

예제 입력 3

2
01
11
5 2

예제 출력 3

5

예제 입력 4

5
11111
11111
10 9

예제 출력 4

0