B. Пропуск
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На улице уже $$$3024$$$ год, идеи для задач давно закончились, а олимпиады теперь проходят в изменённом индивидуальном формате. Олимпиада состоит из $$$n$$$ задач, пронумерованных от $$$1$$$ до $$$n$$$. $$$i$$$-я задача имеет свою стоимость $$$a_i$$$ и некоторый параметр $$$b_i$$$ ($$$1 \le b_i \le n$$$).

Изначально тестирующая система выдаёт участнику первую задачу. Когда участнику выдают $$$i$$$-ю задачу, у него есть два варианта:

  • Либо он сдаёт задачу и получает $$$a_i$$$ баллов;
  • Либо он может пропустить задачу, тогда он никогда не сможет её сдать.

Далее тестирующая система выбирает для участника следующую задачу среди задач с номерами $$$j$$$, такими что:

  • Если он сдал $$$i$$$-ю задачу, она смотрит на задачи с номерами $$$j < i$$$;
  • Если он пропустил $$$i$$$-ю задачу, она смотрит на задачи с номерами $$$j \leq b_i$$$.

Среди этих задач она выбирает задачу с максимальным номером, которую она ранее не выдавала участнику (до этого он её не сдавал и не пропускал). Если такой задачи нет, то соревнование для участника завершается, и его результат равен сумме баллов за все сданные задачи. В частности, если участник сдаёт первую задачу, то соревнование для него завершается. Заметьте, что участник получает каждую задачу максимум один раз.

Прохор тщательно готовился к олимпиаде, и теперь он может сдать любую задачу. Помогите ему определить, какое максимальное количество баллов он может получить.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — стоимости задач.

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

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

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

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

Пример
Входные данные
4
2
15 16
2 1
5
10 10 100 100 1000
3 4 1 1 1
3
100 49 50
3 2 2
4
100 200 300 1000
2 3 4 1
Выходные данные
16
200
100
1000
Примечание

В первом наборе входных данных Прохор может пропустить первую задачу, тогда он получит задачу с номером $$$b_1 = 2$$$. Прохор может сдать её и получить $$$a_2 = 16$$$ баллов. После этого соревнование завершится, потому что Прохор уже получал все задачи. Обратите внимание, что если Прохор сдаст первую задачу, то он получит $$$a_1 = 15$$$ баллов, но соревнование сразу завершится.

Во втором наборе входных данных Прохор может пропустить первую задачу, тогда он получит задачу с номером $$$b_1 = 3$$$. Прохор может сдать её и получить $$$a_3 = 100$$$ баллов. После этого Прохор получит вторую задачу, которую он может пропустить и получить задачу с номером $$$b_2 = 4$$$. Прохор может сдать четвёртую задачу и получить ещё $$$a_4 = 100$$$ баллов. После этого соревнование завершается, потому что Прохор уже получал все задачи с номерами, не превосходящими $$$4$$$. Таким образом, суммарно Прохор получит $$$200$$$ баллов.

В третьем наборе входных данных Прохор может сдать первую задачу и получить $$$100$$$ баллов, после чего соревнование сразу завершится.