На улице уже $$$3024$$$ год, идеи для задач давно закончились, а МКОШП теперь проходит в изменённом индивидуальном формате. Жюри выбирают $$$n$$$ задач из всех, которые когда либо существовали, нумеруют их от $$$1$$$ до $$$n$$$, присваивают каждой задаче стоимость $$$a_i$$$, а так же выбирают для каждой задачи некоторый параметр $$$b_i$$$ от $$$1$$$ до $$$n$$$.
Изначально тестирующая система выдаёт участнику первую задачу. Когда участнику выдают $$$i$$$-ю задачу, у него есть два варианта:
- либо он сдаёт задачу и получает $$$a_i$$$ баллов.
- либо он может скипнуть задачу, тогда он никогда не сможет её сдать.
Далее тестирующая система выбирает для участника следующую задачу среди задач с номерами $$$j$$$, такими что:
- если он сдал задачу, она смотрит на задачи с номерами $$$j \lt i$$$.
- если он скипнул задачу, она смотрит на задачи с номерами $$$j \leqslant b_i$$$.
Среди этих задач она выбирает задачу с максимальным номером, которую она ранее не выдавала участнику (до этого он её не сдавал и не скипал). Если такой задачи нет, то соревнование для участника завершается и его результатом объявляется сумма баллов за все сданные задачи. В частности, если участник сдаёт первую задачу, то соревнование для него завершается.
Прохор очень хочет занять первое место, поэтому он тщательно готовился к этой олимпиаде, он прорешал все существующие задачи и теперь может сдать любую задачу, которую жюри могут выбрать на олимпиаду. Перед олимпиадой он задумался, сколько максимум баллов $$$S$$$ он сможет получить в зависимости от выбора жюри.
К сожалению, Прохор очень устал от решения задач, помогите ему — для каждого выбора жюри ответьте, какой максимальный балл $$$S$$$ сможет получить Прохор.
Каждый тест состоит из нескольких наборов входных данных — выборов жюри. В первой строке находится одно целое число $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ $$$(1 \leq n \leq 4 \cdot 10^5)$$$ — число задач, взятых на олимпиаду.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots , a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — стоимости задач.
Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots , b_n$$$ $$$(1 \leq b_i \leq n)$$$ — параметр задачи.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^5$$$
Для каждого набора входных данных выведите единственное число $$$S$$$ — максимальное число баллов, которое может набрать Прохор.
2215 152 14100 200 300 4003 4 4 1
15 700
В первом случае Прохор может скипнуть первую задачу и система выдаст ему вторую задачу, он может сдать её и получить 15 баллов, далее не выданных задач не остается, соревнование для Прохора завершается с S = 15. Либо Прохор может сдать первую задачу, тоже получить 15 баллов и соревнование завершится.
Во втором случае Прохор скипает первую, переходит к третьей (она ранее не выдавалась), сдаёт её и получает 300 баллов, так как вторая задача ранее не выдавалась он переходит к ней, скипает её и переходит к четвёртой (она ранее не выдавалась), сдаёт четвёртую и получает ещё 400 баллов, не выданных задач не осталось, соревнование для Прохора завершается с S = 700.
| Name |
|---|