排队游戏

题目描述

身高是一个敏感的问题...

SYNU新生们正在军训，一共有 $n$ 位新生，每个人都有一个身高，第 $i$ 位同学的身高记为 $a_i$，教官让他们站成一排，记作队列 $A$，此时另外一名教官带着另外 $n$ 名新生来了，他们每个人的身高记为 $b_i$，他们要按照如下规则进行一个排队游戏，对于新来的第 $i$ 名新生，你需要找到 $A$ 中前 $i$ 位新生中身高不超过 $b_i$ 的最高的一位新生，此时将他从 $A$ 中去掉，并让当前的这位新生代替他的位置，即 $a_i \gets b_i$。若 $A$ 的前 $i$ 位新生中没有符合条件的新生，则什么都不做。请问最后排队完成之后，队列 $A$ 的所有成员身高之和为多少？

输入格式

输入共包含若干行，第一行包含一个整数 $T$，表示测试用例的组数。接下来每个测试用例包含 $n + 2$ 行，第一行为一个整数 $n(n \leq 2 \times 10^5)$，表示原队列 $A$ 中每个人的身高，接下来一行包含 $n$ 个整数 $a_i(a_i \leq 10^9)$，表示原队列 $A$ 中每个人的身高，接下来有 $n$ 行，第 $i$ 行包含一个整数 $b_i(b_i \leq 10^9)$，表示要插入的人的身高。

测试用例保证 $\sum n\leq 10^6$。

输出格式

对于每一个测试用例，输出一个答案。

样例 #1

样例输入 #1

1
5
1 2 5 3 7
2
1
4
5
9

样例输出 #1

23

提示

对于测试用例1：

原序列为1 2 5 3 7

第1次插入2，序列中前1个元素中不超过2的最大值为1;将1替换成2;此时变成2 2 5 3 7.

第2次插入1，序列前2个元素中不存在不超过1的数，本次插入结束.

第3次插入4，序列变成2 4 5 3 7.

第4次插入5，序列变成2 4 5 3 7.

第5次插入9，序列变成2 4 5 3 9.

最后序列的和为23.