У Маленької Ціанової Рибки є дві світлодіодні стрічки, кожна з яких містить $n$ лампочок, пронумерованих від $1$ до $n$. Кожна лампочка або увімкнена, або вимкнена. Початкові стани двох стрічок описуються двійковими рядками $a$ і $b$ довжини $n$, де 1 позначає увімкнену лампочку, а 0 позначає вимкнену лампочку.

Є $n + 1$ інтерфейсів керування, пронумерованих від $0$ до $n$. Інтерфейс $0$ знаходиться перед першою лампочкою, а інтерфейс $i$ знаходиться одразу після лампочки $i$ для кожного $1 \le i \le n$. Інтерфейс $i$ має параметр вартості $c_i$.

За одну операцію Маленька Ціанова Рибка обирає два інтерфейси $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$), що позначає кількість лампочок на кожній стрічці.

Другий і третій рядки містять двійкові рядки $a$ і $b$ довжини $n$ відповідно, які складаються лише з символів 0 та 1.

Четвертий рядок містить $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

Примітка

У першому тестовому прикладі всі лампочки вже вимкнені, тому жодних операцій не потрібно.

У другому тестовому прикладі Маленька Ціанова Рибка обирає інтерфейси $0$ та $1$ і перемикає обидві лампочки. Ця операція коштує $\max(7, 9) = 9$.

У третьому тестовому прикладі він спочатку перемикає всі лампочки на першій стрічці, використовуючи інтерфейси $0$ та $3$, вартістю $1$. Потім він перемикає її середню лампочку, використовуючи інтерфейси $1$ та $2$, вартістю $100$. Загальна вартість становить $101$.