Little Cyan Fish có hai dải đèn, mỗi dải gồm $n$ bóng đèn được đánh số từ $1$ đến $n$. Mỗi bóng đèn ở trạng thái bật hoặc tắt. Trạng thái ban đầu của hai dải đèn được mô tả bởi hai xâu nhị phân $a$ và $b$ có độ dài $n$, trong đó 1 biểu thị bóng đèn đang bật và 0 biểu thị bóng đèn đang tắt.

Có $n + 1$ giao diện điều khiển, được đánh số từ $0$ đến $n$. Giao diện $0$ nằm trước bóng đèn đầu tiên, và giao diện $i$ nằm ngay sau bóng đèn $i$ với mỗi $1 \le i \le n$. Giao diện $i$ có một tham số chi phí là $c_i$.

Trong một thao tác, Little Cyan Fish chọn hai giao diện $p$ và $q$ ($0 \le p < q \le n$) và thực hiện một trong các hành động sau:

• Đảo trạng thái tất cả các bóng đèn được đánh số $p + 1, p + 2, \dots, q$ trên dải thứ nhất;
• Đảo trạng thái tất cả các bóng đèn được đánh số $p + 1, p + 2, \dots, q$ trên dải thứ hai;
• Đảo trạng thái tất cả các bóng đèn được đánh số $p + 1, p + 2, \dots, q$ trên cả hai dải.

Việc đảo trạng thái một bóng đèn sẽ thay đổi trạng thái của nó từ bật sang tắt hoặc từ tắt sang bật. Mỗi hành động trong ba hành động trên đều có chi phí là $\max(c_p, c_q)$. Các giao diện có thể được sử dụng lặp lại nhiều lần và không có giới hạn về số lượng thao tác.

Hãy tìm tổng chi phí nhỏ nhất cần thiết để tắt tất cả các bóng đèn trên cả hai dải.

Dữ liệu vào

Có nhiều bộ dữ liệu kiểm tra. Dòng đầu tiên của dữ liệu vào chứa một số nguyên dương $T$ ($1 \le T$), cho biết số lượng bộ dữ liệu kiểm tra.

Đối với mỗi bộ dữ liệu kiểm tra, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 3 \times 10^5$), cho biết số lượng bóng đèn trên mỗi dải.

Dòng thứ hai và dòng thứ ba lần lượt chứa hai xâu nhị phân $a$ và $b$ có độ dài $n$, chỉ bao gồm các ký tự 0 và 1.

Dòng thứ tư chứa $n + 1$ số nguyên $c_0, c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), cho biết các tham số chi phí của các giao diện.

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu kiểm tra không vượt quá $3 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu kiểm tra, in ra một dòng chứa một số nguyên duy nhất, cho biết tổng chi phí nhỏ nhất cần thiết để tắt tất cả các bóng đèn trên cả hai dải.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

0
9
101

Ghi chú

Trong bộ dữ liệu kiểm tra mẫu thứ nhất, tất cả các bóng đèn đều đã tắt sẵn, vì vậy không cần thực hiện thao tác nào.

Trong bộ dữ liệu kiểm tra mẫu thứ hai, Little Cyan Fish chọn giao diện $0$ và $1$ rồi đảo trạng thái cả hai bóng đèn. Thao tác này có chi phí là $\max(7, 9) = 9$.

Trong bộ dữ liệu kiểm tra mẫu thứ ba, đầu tiên cậu ấy đảo trạng thái tất cả các bóng đèn trên dải thứ nhất bằng cách sử dụng giao diện $0$ và $3$, với chi phí là $1$. Sau đó cậu ấy đảo trạng thái bóng đèn ở giữa của dải đó bằng cách sử dụng giao diện $1$ và $2$, với chi phí là $100$. Tổng chi phí là $101$.