← 返回题目列表

Codeforces · 2023/B

B. 跳过

中文机器翻译题面 查看原题

今年已经是$$$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$$$ 的问题。

在这些问题中,它选择之前没有给参与者的最大索引的问题(他之前既没有提交也没有跳过)。如果没有该问题,则参赛者的比赛结束,其成绩等于所有提交问题的得分总和。特别是,如果参赛者提交了第一个问题,那么他们的比赛就结束了。请注意,参与者最多收到每个问题一次。

Prokhor已经为奥运会做好了充分的准备,现在他可以提交任何问题。帮助他确定他可以获得的最大分数。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,输出一个整数 - Prokhor 可以达到的最大点数。

示例

输入 #1

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

输出 #1

16
200
100
1000

注意

在第一个测试用例中,Prokhor可以跳过第一个问题;那么他将收到索引 $$$b_1 = 2$$$ 的问题。 Prokhor 可以提交并获得 $$$a_2 = 16$$$ 积分。之后,比赛将结束,因为 Prokhor 已经收到了所有问题。请注意,如果 Prokhor 提交了第一个问题,他将获得 $$$a_1 = 15$$$ 分,但比赛将立即结束。

在第二个测试用例中,Prokhor可以跳过第一个问题;那么他将收到索引 $$$b_1 = 3$$$ 的问题。 Prokhor 可以提交并获得 $$$a_3 = 100$$$ 积分。之后,Prokhor 将收到第二个问题,他可以跳过该问题以接收索引为 $$$b_2 = 4$$$ 的问题。 Prokhor 可以提交第四个问题并获得另外 $$$a_4 = 100$$$ 积分。之后,比赛结束,因为 Prokhor 已经收到了所有指数不超过 $$$4$$$ 的问题。因此,Prokhor 将获得总共 $$$200$$$ 积分。

在第三个测试用例中,Prokhor 可以提交第一个问题并获得 $$$100$$$ 积分,之后比赛将立即结束。