G. Два символа, два цвета
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка, состоящая из символов 0 и/или 1. Вам нужно покрасить каждый символ этой строки в один из двух цветов: красный или синий.

Если вы покрасите $$$i$$$-й символ в красный цвет, вы получите $$$r_i$$$ монет. Если вы покрасите его в синий цвет, вы получите $$$b_i$$$ монет.

После покраски строки из нее удаляются все символы синего цвета. Затем в полученной строке подсчитывается количество инверсий (т. е. количество пар символов, в которых левый символ в паре — 1, а правый символ — 0). За каждую инверсию вы должны заплатить $$$1$$$ монету.

Какое максимальное количество монет вы можете заработать?

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из четырех строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — длину строки;
  • вторая строка содержит $$$s$$$ — последовательность из $$$n$$$ символов, где каждый символ либо 0, либо 1;
  • третья строка содержит $$$n$$$ целых чисел $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^{12}$$$);
  • четвертая строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^{12}$$$).

Дополнительное ограничение на входные данные: сумма значений $$$n$$$ по всем наборам входных данных не превышает $$$4 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество монет, которое вы можете заработать.

Пример
Входные данные
4
7
0100010
6 6 6 7 7 6 6
3 3 5 4 7 6 7
5
10111
9 8 5 7 5
4 4 7 8 4
10
0100000000
7 7 6 5 2 2 5 3 8 3
8 6 9 6 6 8 9 7 7 9
8
01010000
8 7 7 7 8 7 7 8
4 4 4 2 1 4 4 4
Выходные данные
43
36
76
52
Примечание

Пояснения для наборов входных данных в примере из условия (синие символы подчеркнуты, красные — нет):

  1. $$$0100\underline{0}1\underline{0}$$$;
  2. $$$10\underline{11}1$$$;
  3. $$$\underline{0}1\underline{00000000}$$$;
  4. $$$0\underline{1}010000$$$.