A. Упоротая слава
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Герой очень хочет славы, поэтому он сражается с монстрами.

У героя есть $$$n$$$ способностей. $$$i$$$-я способность имеет тип $$$a_i$$$ (любой из огонь или мороз) и исходный урон $$$b_i$$$.

Герой может использовать все $$$n$$$ способностей в любом порядке (каждая способность будет использована только один раз). При использовании каждой способности, происходит следующее:

  • Если текущая способность следует сразу за способностью другого типа, то её урон удваивается.
Другими словами,
  1. Если способность типа огонь с исходным уроном $$$c$$$ используется сразу после способности с типом огонь, тогда она нанесет $$$c$$$ урона;
  2. Если способность типа огонь с исходным уроном $$$c$$$ используется сразу после способности с типом мороз, тогда она нанесет $$$2c$$$ урона;
  3. Если способность типа мороз с исходным уроном $$$c$$$ используется сразу после способности с типом огонь, тогда она нанесет $$$2c$$$ урона;
  4. Если способность типа мороз с исходным уроном $$$c$$$ используется сразу после способности с типом мороз, тогда она нанесет $$$c$$$ урона.

Ваша задача найти максимальный урон, который может нанести герой.

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

В первой строке задано целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Затем следуют описания наборов входных данных.

В первой строке задано целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$), означающее количество способностей.

Во второй строке задано $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 1$$$), где $$$a_i$$$ означает тип $$$i$$$-й способности. $$$i$$$-я способность имеет тип огонь, если $$$a_i = 0$$$, и тип мороз, если $$$a_i = 1$$$.

В третьей строке задано $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$), где $$$b_i$$$ означает исходный урон $$$i$$$-й способности.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите максимальный урон, который может нанести герой.

Пример
Входные данные
4
4
0 1 1 1
1 10 100 1000
6
0 0 0 1 1 1
3 4 5 6 7 8
3
1 1 1
1000000000 1000000000 1000000000
1
1
1
Выходные данные
2112
63
3000000000
1
Примечание

В первом наборе входных данных мы можем применить способности в порядке $$$[3, 1, 4, 2]$$$, и суммарный урон будет $$$100 + 2 \times 1 + 2 \times 1000 + 10 = 2112$$$.

Во втором наборе входных данных мы можем применить способности в порядке $$$[1, 4, 2, 5, 3, 6]$$$, и суммарный урон будет $$$3 + 2 \times 6 + 2 \times 4 + 2 \times 7 + 2 \times 5 + 2 \times 8 = 63$$$.

В третьем наборе входных данных мы можем применить способности в порядке $$$[1, 2, 3]$$$, и суммарный урон будет $$$1000000000 + 1000000000 + 1000000000 = 3000000000$$$.

В четвертом примере всего одна способность с уроном $$$1$$$, значит суммарный урон будет $$$1$$$.