비트 변환 비용

$1$번부터 $n$번까지 번호가 붙은 비트 $n$개가 있다. 비트 $i$의 처음 값은 $0$ 또는 $1$인 $a_i$이고, 비용은 $c_i$이다.

연산 한 번은 비트 $i$를 하나 골라 그 값을 뒤집는다. $0$은 $1$이 되고, $1$은 $0$이 된다. 이 연산의 가격은 뒤집은 뒤에 값이 $1$인 모든 비트 $j$의 $c_j$를 더한 값이다. 비트 $i$가 $1$이 되었다면 그 비트의 비용 $c_i$도 이 합에 들어간다.

어떤 비트든 원하는 순서로 몇 번이든 연산할 수 있다. 모든 $i$에 대해 비트 $i$의 값을 $b_i$로 만드는 가격의 합 중 최솟값을 구하여라.

첫째 줄에 비트의 개수 $n$이 주어진다. ($1 \le n \le 5\,000$)

둘째 줄에 각 비트의 비용 $c_1, c_2, \dots, c_n$이 주어진다. ($1 \le c_i \le 10^9$)

셋째 줄에 처음 값을 나타내는 길이 $n$짜리 문자열 $a_1 a_2 \dots a_n$이 주어진다.

넷째 줄에 목표 값을 나타내는 길이 $n$짜리 문자열 $b_1 b_2 \dots b_n$이 주어진다.

가격의 합 중 최솟값을 첫째 줄에 출력한다.