Little Cyan Fish에게는 두 개의 조명 스트립이 있으며, 각 스트립에는 $1$부터 $n$까지 번호가 매겨진 $n$개의 전구가 있습니다. 각 전구는 켜져 있거나 꺼져 있습니다. 두 스트립의 초기 상태는 길이가 $n$인 이진 문자열 $a$와 $b$로 설명되며, 여기서 1은 켜진 전구를 나타내고 0은 꺼진 전구를 나타냅니다.

$0$부터 $n$까지 번호가 매겨진 $n + 1$개의 제어 인터페이스가 있습니다. 인터페이스 $0$은 첫 번째 전구 앞에 있으며, 각 $1 \le i \le n$에 대해 인터페이스 $i$는 전구 $i$ 바로 뒤에 있습니다. 인터페이스 $i$는 비용 매개변수 $c_i$를 가집니다.

한 번의 연산에서 Little Cyan Fish는 두 인터페이스 $p$와 $q$ ($0 \le p < q \le n$)를 선택하고 다음 동작 중 하나를 수행합니다:

• 첫 번째 스트립에서 번호가 $p + 1, p + 2, \dots, q$인 모든 전구의 상태를 반전시킵니다.
• 두 번째 스트립에서 번호가 $p + 1, p + 2, \dots, q$인 모든 전구의 상태를 반전시킵니다.
• 두 스트립 모두에서 번호가 $p + 1, p + 2, \dots, q$인 모든 전구의 상태를 반전시킵니다.

전구의 상태를 반전시키면 상태가 켜짐에서 꺼짐으로, 또는 꺼짐에서 켜짐으로 바뀝니다. 세 가지 동작은 각각 $\max(c_p, c_q)$의 비용이 듭니다. 인터페이스는 반복해서 사용할 수 있으며, 연산 횟수에는 제한이 없습니다.

두 스트립의 모든 전구를 끄기 위해 필요한 최소 총비용을 구하세요.

입력

테스트 케이스가 여러 개 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 단일 정수 $T$ ($1 \le T$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 각 스트립에 있는 전구의 수를 나타내는 단일 정수 $n$ ($1 \le n \le 3 \times 10^5$)이 주어집니다.

두 번째 줄과 세 번째 줄에는 각각 길이가 $n$이고 문자 0과 1로만 이루어진 이진 문자열 $a$와 $b$가 주어집니다.

네 번째 줄에는 인터페이스의 비용 매개변수를 나타내는 $n + 1$개의 정수 $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$)이 주어집니다.

모든 테스트 케이스에 대한 $n$의 합은 $3 \times 10^5$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스마다 두 스트립의 모든 전구를 끄기 위해 필요한 최소 총비용을 나타내는 단일 정수를 한 줄에 출력합니다.

예제

입력 1

3
1
0
0
1 1
1
1
1
7 9
3
101
000
1 100 100 1

출력 1

0
9
101

참고

첫 번째 예제 테스트 케이스에서는 모든 전구가 이미 꺼져 있으므로 어떠한 연산도 필요하지 않습니다.

두 번째 예제 테스트 케이스에서 Little Cyan Fish는 인터페이스 $0$과 $1$을 선택하여 두 전구를 모두 반전시킵니다. 이 연산의 비용은 $\max(7, 9) = 9$입니다.

세 번째 예제 테스트 케이스에서 그는 먼저 인터페이스 $0$과 $3$을 사용하여 비용 $1$로 첫 번째 스트립의 모든 전구를 반전시킵니다. 그런 다음 인터페이스 $1$과 $2$를 사용하여 비용 $100$으로 가운데 전구를 반전시킵니다. 총비용은 $101$입니다.