C. Магазин ограниченной серии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
cYsmix - House With Legs
⠀

Существует магазин с $$$n$$$ объектами, пронумерованными от $$$1$$$ до $$$n$$$, и есть только одна копия каждого объекта. По вашему мнению, объекты имеют ценности $$$v_1, v_2, \ldots, v_n$$$ (которые могут быть отрицательными).

У Алисы и Боба есть свои собственные предпочтения объектов ($$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$ соответственно). В частности, любимый объект Алисы — это $$$a_1$$$, затем $$$a_2$$$ и так далее; любимый объект Боба — это $$$b_1$$$, затем $$$b_2$$$ и так далее.

$$$n$$$ раз один из них заходит в магазин и покупает свой самый любимый объект, который все еще есть в магазине. В конце у Алисы и Боба есть свои собственные наборы объектов.

Теперь магазин пуст, и вам интересно, насколько предпочтения Алисы похожи на ваши. Среди всех наборов объектов, которые могла бы купить Алиса, какова максимальная сумма значений по вашему мнению?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество объектов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$v_1, v_2, \ldots, v_n$$$ ($$$-10^9 \le v_i \le 10^9$$$) — значения объектов по вашему мнению.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — порядок предпочтений Алисы. Числа $$$a_i$$$ различны.

Четвертая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — порядок предпочтений Боба. Числа $$$b_i$$$ различны.

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

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

Для каждого набора входных данных выведите одно целое число: максимальную сумму значений среди всех наборов объектов, которые могла бы купить Алиса.

Пример
Входные данные
8
3
1 -1 1
3 1 2
2 3 1
3
-2 5 2
3 1 2
2 3 1
3
-1 -2 -3
3 1 2
2 3 1
3
1000000000 1000000000 1000000000
3 1 2
2 3 1
4
5 -15 10 -5
2 4 3 1
1 4 2 3
4
-5 -5 -5 100
2 3 1 4
4 1 2 3
4
-1 -100 5 10
1 2 3 4
2 3 4 1
12
-4 6 10 10 1 -8 6 2 -8 -4 0 -6
11 12 7 3 6 8 1 5 10 2 9 4
7 5 3 6 1 2 8 12 9 4 10 11
Выходные данные
2
5
0
3000000000
10
85
14
24
Примечание

В первом наборе входных данных Алиса может купить наборы объектов $$$[]$$$ (пустой), $$$[1]$$$, $$$[3]$$$, $$$[3, 1]$$$, $$$[3, 1, 2]$$$ (объекты упорядочены по времени покупки). Например, чтобы Алиса купила $$$[1]$$$, двое могут зайти в магазин в следующем порядке:

  • Боб заходит и покупает объект $$$2$$$;
  • Боб заходит и покупает объект $$$3$$$ (объект $$$2$$$ распродан);
  • Алиса заходит и покупает объект $$$1$$$ (объект $$$3$$$ распродан).

Набор объектов с максимальной общей стоимостью по вашему мнению — это $$$[3, 1]$$$, и он имеет значение $$$v_3 + v_1 = 2$$$.

Во втором наборе входных данных предпочтения Алисы и Боба такие же, как в первом наборе входных данных, но теперь набор объектов с максимальной общей стоимостью — это $$$[3, 1, 2]$$$, со стоимостью $$$5$$$.