У Маленькой Циановой Рыбки есть две светодиодные ленты, каждая из которых содержит $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$.