34699번 - 구간 NOT 과 단일 NOT

문제

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ドル$로 만드는 데 필요한 최소 비용을 출력한다.

제한

노트