P17879 子序列 / sequence

对于序列 $a$，定义 $[a_{p_1},a_{p_2},a_{p_3},\ldots,a_{p_m}]$ $(1\le p_1

**本题包含多组测试数据。** 输入的第一行包含两个非负整数 $c, t$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： - 第一行包含一个正整数 $n$，代表序列长度。 - 第二行包含一个长度为 $n$ 的正整数序列 $a$。 - 第三行包含一个长度为 $n$ 的整数序列 $b$。

对于每组测试数据，输出一行一个数，代表所有好子序列中，$b_{p_1}+b_{p_2}+b_{p_3}+\ldots+b_{p_m}$ 的最大值。

**【样例 1 解释】** 对于第一组测试数据，$[1,1]$ 的任意非空子序列都是不下降的，其唯一的极长不下降子序列就是它本身。因此，只能选取空子序列，答案为 $0$。 对于第二组测试数据，$[2,1]$ 是唯一的非空好子序列，其中 $[2]$ 和 $[1]$ 是两个不相交的极长不下降子序列。选取 $[2,1]$ 的权值和为 $-3+2=-1$，选取空子序列的权值和为 $0$，故答案为 $0$。 对于第三组测试数据，选取整个序列 $[4,3,1,2]$。其中，$[4]$、$[3]$ 和 $[1,2]$ 均为极长不下降子序列，任取两个都不相交，故整个序列是好的。全部四项的权值均为正，答案为 $1+2+3+4=10$。 对于第四组测试数据，若选取第 $1$ 项，则由于它位于所选子序列的开头且值最小，每个极长不下降子序列都包含这一项。若不选第 $4$ 项，则所选各项构成不下降序列。因此，非空好子序列必须舍去第 $1$ 项并选取第 $4$ 项。选取第 $2,4$ 项可得好子序列 $[3,2]$，权值和为 $8-1=7$。剩下的第 $3$ 项权值为 $-2$，故答案为 $7$。 对于第五组测试数据，选取整个序列 $[2,3,1,2]$。第 $1,2$ 项组成的 $[2,3]$ 与第 $3,4$ 项组成的 $[1,2]$ 均为极长不下降子序列。两者中的 $2$ 分别位于第 $1$ 项和第 $4$ 项，下标集合 $\{1,2\}$ 与 $\{3,4\}$ 不相交，故整个序列是好的。答案为 $4\times 10^9=4000000000$。 **【样例 2】** 见选手目录下的 `sequence/sequence2.in` 与 `sequence/sequence2.ans`。 该样例满足测试点 $1$ 的条件限制。 **【样例 3】** 见选手目录下的 `sequence/sequence3.in` 与 `sequence/sequence3.ans`。 该样例满足测试点 $2\sim 3$ 的条件限制。 **【样例 4】** 见选手目录下的 `sequence/sequence4.in` 与 `sequence/sequence4.ans`。 该样例满足测试点 $4\sim 5$ 的条件限制。 **【样例 5】** 见选手目录下的 `sequence/sequence5.in` 与 `sequence/sequence5.ans`。 该样例满足测试点 $6\sim 8$ 的条件限制。 **【样例 6】** 见选手目录下的 `sequence/sequence6.in` 与 `sequence/sequence6.ans`。 该样例满足测试点 $9\sim 10$ 的条件限制。 **【样例 7】** 见选手目录下的 `sequence/sequence7.in` 与 `sequence/sequence7.ans`。 该样例满足测试点 $11$ 的条件限制。 **【样例 8】** 见选手目录下的 `sequence/sequence8.in` 与 `sequence/sequence8.ans`。 该样例满足测试点 $12$ 的条件限制。 **【样例 9】** 见选手目录下的 `sequence/sequence9.in` 与 `sequence/sequence9.ans`。 该样例满足测试点 $13\sim 14$ 的条件限制。 **【样例 10】** 见选手目录下的 `sequence/sequence10.in` 与 `sequence/sequence10.ans`。 该样例满足测试点 $15\sim 17$ 的条件限制。 **【样例 11】** 见选手目录下的 `sequence/sequence11.in` 与 `sequence/sequence11.ans`。 该样例满足测试点 $18\sim 19$ 的条件限制。 **【样例 12】** 见选手目录下的 `sequence/sequence12.in` 与 `sequence/sequence12.ans`。 该样例满足测试点 $20\sim 21$ 的条件限制。 **【样例 13】** 见选手目录下的 `sequence/sequence13.in` 与 `sequence/sequence13.ans`。 该样例满足测试点 $22\sim 25$ 的条件限制。 **【数据范围】** 设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，均有： - $1\le t\le 10^4$； - $2\le n\le 10^6$，$N\le 3\times 10^6$； - 对于所有 $1\le i\le n$，均有 $1\le a_i\le n$； - 对于所有 $1\le i\le n$，均有 $|b_i|\le 10^9$。 ::cute-table{tuack} |测试点编号 |$n\le$ |$N\le$ |特殊性质| |:--------:|:------:|:--------:|:--:| |$1$ |$2$ |$2\times 10^4$|无 | |$2,3$ |$10$ |$50$ |^ | |$4,5$ |$20$ |$100$ |^ | |$6\sim 8$ |$500$ |$2\,000$ |^ | |$9,10$ |$5\,000$|$1.5\times 10^4$|AB | |$11$ |^ |^ |A | |$12$ |^ |^ |B | |$13,14$ |^ |^ |C | |$15\sim 17$|^ |^ |无 | |$18,19$ |$10^6$ |$3\times 10^6$|B | |$20,21$ |^ |^ |C | |$22\sim 25$|^ |^ |无 | 特殊性质 A：对于所有 $1\le i