题目描述

江桥又来到了他的花园，这次他准备采摘 $m$ 朵花。

花园的花朵从左到右依次排列，第 $i$ 朵花的美丽值为 $a_i$。

江桥将会从左走到右，按顺序依次决定每朵花是否采摘。

他最终会采摘 $m$ $(m \leq n)$ 朵花，但是要求第 $i$ 朵采摘的花朵美丽值至少为 $b_i$。

江桥从魔法学院学会了魔法，他可以使用最多 $1$ 次魔法，使用魔法会花费 $k$ 点魔力值使得花园里增加一朵美丽值为 $k$ 的花朵。这朵花可以出现在任意一朵花的左边或者右边（即可以出现在第 $1$ 朵花的左边的位置、第 $n$ 朵花的右边位置，或中间某一个位置）。

请你帮江桥计算出，他最少需要花费多少魔力值，或者告诉他他的采摘计划是不可能完成的。

输入格式

输入包含多组数据。第一行一个正整数 $T$ 表示数据组数。对于每组数据：

第一行输入两个正整数 $n,m$，表示花园的花朵总数和江桥要采摘的数量。

接下来一行 $n$ 个正整数表示 $a_i$。

接下来一行 $m$ 个正整数表示 $b_i$。

请使用较快的读入方式。

输出格式

如果使用魔法后依然无法完成采摘计划，输出 -1，如果不需要使用魔法，则输出 0，否则输出最少需要花费多少魔力值。

7
9 5
3 5 2 3 3 5 8 1 2
4 6 2 4 6
6 3
1 2 6 8 2 1
5 4 3
5 3
4 3 5 4 3
7 4 5
6 3
8 4 2 1 2 5
6 1 4
5 5
1 2 3 4 5
5 4 3 2 1
6 3
1 2 3 4 5 6
9 8 7
5 5
7 7 6 7 7
7 7 7 7 7

6
3
7
0
-1
-1
7

样例解释

在第一个测试案例中，假设江桥种植了一朵美丽的花 $6$ ，并把它放在第三朵花和第四朵花之间。那么，花园就会变成下面的样子： $[3, 5, 2, 6, 3, 3, 5, 8, 1, 2]$ .然后，他可以选择第二、第四、第六、第七和第八朵美丽的花朵 $[5, 6, 3, 5, 8]$ 。

在第三个测试案例中，他可以种植一朵美丽的花朵 $7$ ，并把它放在第一朵花朵之前。花园就会变成下面的样子： $[7, 4, 3, 5, 4, 3]$ .现在，他可以选择第一朵、第二朵和第四朵花。

在第四个测试用例中，江桥不需要使用魔法，因此答案为 $0$ 。

在第六个测试用例中，无论江桥如何进行魔法，他都无法收集到 $3$ 朵花，使得他收集到的第 $i$ 朵花的美丽程度至少为 $b_i$ ，因此答案为 $-1$ 。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq t \leq 10^4,1 \leq n,m,\sum n,\sum m \leq 2 \times 10^{6},m \leq n,1 \leq a_i,b_i \leq 10^9$。