题目描述

现在已经是 3024 年，出题思路早就枯竭了，奥林匹克竞赛改成了一种改良的个人赛形式。这场竞赛一共有 $n$ 道题目，编号从 $1$ 到 $n$。第 $i$ 道题有分值 $a_i$ 和一个参数 $b_i$（$1 \le b_i \le n$）。

一开始，评测系统会把第 1 题交给选手。当选手拿到第 $i$ 题时，有两种选择：

• 提交这道题，得到 $a_i$ 分；
• 跳过这道题，之后永远不能再提交它。

做完选择之后，系统按照下面的规则，从还没有发放过的题目里选出下一题：

• 如果选手提交了第 $i$ 题：只考虑下标满足 $j < i$ 的题目；
• 如果选手跳过了第 $i$ 题：只考虑下标满足 $j \le b_i$ 的题目。

在符合条件、并且还没有发放给选手（既没有提交也没有跳过）的题目中，系统挑选下标最大的那一道作为下一题。如果不存在这样的题目，比赛直接结束，选手总分等于所有提交题目的分数之和。特别注意：如果选手提交了第 1 题，比赛会立刻结束。每一道题目最多只会发放给选手一次。

普罗霍尔已经充分备战，所有题目他都可以做对并提交。请你帮他求出能够拿到的最大总分。

输入格式

多组测试用例。第一行一个整数 $t$（$1 \le t \le 10^5$），代表测试用例数量。

每组测试用例第一行输入一个整数 $n$（$1 \le n \le 4\cdot 10^5$），代表题目总数。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$），代表每道题的分值。

第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$（$1 \le b_i \le 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

说明

第一组测试用例：普罗霍尔可以跳过第 1 题，之后系统发放 $b_1=2$ 也就是第 2 题。他提交第 2 题得到 $16$ 分，之后所有题目都已经发放完毕，比赛结束。如果他选择提交第 1 题，只能拿到 $15$ 分并且比赛立刻结束。

第二组测试用例：普罗霍尔跳过第 1 题，拿到第 3 题，提交获得 $100$ 分；接下来发放第 2 题，他选择跳过，于是拿到 $b_2=4$ 也就是第 4 题，提交再拿 $100$ 分。此时所有下标不超过 $4$ 的题目都已经发放完毕，比赛结束，总分为 $200$。

第三组测试用例：普罗霍尔直接提交第 1 题，拿到 $100$ 分，比赛立刻结束。

原题链接

原题链接