Задача №115384. Скип или не скип
На улице уже \(3024\) год, идеи для задач давно закончились, а МКОШП теперь проходит в изменённом индивидуальном формате. Жюри выбирают \(n\) задач из всех, которые когда либо существовали, нумеруют их от \(1\) до \(n\), присваивают каждой задаче стоимость \(a_i\), а так же выбирают для каждой задачи некоторый параметр \(b_i\) от \(1\) до \(n\).
Изначально тестирующая система выдаёт участнику первую задачу. Когда участнику выдают \(i\)-ю задачу, у него есть два варианта:
-
либо он сдаёт задачу и получает \(a_i\) баллов.
-
либо он может скипнуть задачу, тогда он никогда не сможет её сдать.
Далее тестирующая система выбирает для участника следующую задачу среди задач с номерами \(j\), такими что:
-
если он сдал задачу, она смотрит на задачи с номерами \(j < 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\) — максимальное число баллов, которое может набрать Прохор.
В первом случае Прохор может скипнуть первую задачу и система выдаст ему вторую задачу, он может сдать её и получить 15 баллов, далее не выданных задач не остается, соревнование для Прохора завершается с S = 15. Либо Прохор может сдать первую задачу, тоже получить 15 баллов и соревнование завершится.
Во втором случае Прохор скипает первую, переходит к третьей (она ранее не выдавалась), сдаёт её и получает 300 баллов, так как вторая задача ранее не выдавалась он переходит к ней, скипает её и переходит к четвёртой (она ранее не выдавалась), сдаёт четвёртую и получает ещё 400 баллов, не выданных задач не осталось, соревнование для Прохора завершается с S = 700.
2 2 15 15 2 1 4 100 200 300 400 3 4 4 1
15 700