当前没有测试数据。

D. Flower Boy

题目描述

花男孩有一个种有 $n$ 朵花的花园，这些花可以用一个整数序列 $a_1, a_2, \dots, a_n$ 表示，其中 $a_i$ 是从左到右第 $i$ 朵花的美丽值。

Igor 想要恰好收集 $m$ 朵花。他会从左到右走过花园，选择是否收集当前位置的花。他收集到的第 $i$ 朵花，其美丽值必须至少为 $b_i$。

Igor 发现，可能无法收集到满足美丽值要求的 $m$ 朵花。因此，在开始收集之前，他可以选择任意整数 $k$，使用魔法棒新增一朵美丽值为 $k$ 的花，并将其放置在花园的任意位置（两朵花之间、第一朵花之前或最后一朵花之后）。由于魔法能力有限，他最多只能使用一次这个操作。

请输出 Igor 为了确保能收集到 $m$ 朵花，在使用该操作时必须选择的最小整数 $k$。如果不使用该操作就能收集到 $m$ 朵花，输出 $0$。如果即使使用了该操作也无法收集到 $m$ 朵花，输出 $-1$。

输入格式

第一行输入一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 2 \cdot 10^5$）—— 花园中花的总数和 Igor 想要收集的花的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 从左到右每朵花的美丽值。

每个测试用例的第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \le b_i \le 10^9$）—— Igor 收集的第 $i$ 朵花必须满足的最小美丽值。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，单独输出一行结果：

• 若无需使用魔法操作即可收集到 $m$ 朵花，输出 $0$；
• 若必须使用魔法操作，输出最小的 $k$；
• 若使用魔法操作后仍无法收集到 $m$ 朵花，输出 $-1$。

样例输入

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

样例解释

测试用例 1

Igor 新增一朵美丽值为 6 的花，放置在第 3 朵和第 4 朵花之间。此时花园序列变为 $[3, 5, 2, 6, 3, 3, 5, 8, 1, 2]$。他可以收集第 2、4、6、7、8 朵花，美丽值分别为 $[5, 6, 3, 5, 8]$，满足 $b = [4, 6, 2, 4, 6]$ 的要求。

测试用例 2

无需额外解释（输出 3 是满足条件的最小 k）。

测试用例 3

Igor 新增一朵美丽值为 7 的花，放置在第一朵花之前。此时花园序列变为 $[7, 4, 3, 5, 4, 3]$。他可以收集第 1、2、4 朵花，美丽值分别为 $[7, 4, 5]$，满足 $b = [7, 4, 5]$ 的要求。

测试用例 4

不使用魔法操作即可满足要求。原花园序列 $[8, 4, 2, 1, 2, 5]$ 中，可收集第 1、2、6 朵花，美丽值 $[8, 4, 5]$ 满足 $b = [6, 1, 4]$ 的要求，因此输出 0。

测试用例 5

原序列 $[1, 2, 3, 4, 5]$ 需收集 5 朵花，且第 $i$ 朵花的美丽值至少为 $b_i = [5, 4, 3, 2, 1]$。即使新增一朵花，也无法让收集到的 5 朵花按顺序满足 $b_1 \le 5$（原序列最大为 5，但需作为第 1 朵收集，后续 4 朵需满足 4、3、2、1，看似可行？实际原序列的 5 是第 5 朵，若不新增，收集顺序为 5、4、3、2、1，对应的美丽值是 5、4、3、2、1，刚好满足？但样例输出为 -1，可能我的理解有误，实际需严格按原序列从左到右收集，即收集的花的位置必须递增。原序列中，要收集 5 朵花，需按顺序选择 5 个位置 $i_1 < i_2 < i_3 < i_4 < i_5$，使得 $a_{i_1} \ge 5$、$a_{i_2} \ge 4$、$a_{i_3} \ge 3$、$a_{i_4} \ge 2$、$a_{i_5} \ge 1$。原序列中 $a_{i_1} \ge 5$ 只有第 5 朵花（值为 5），但后续无更多花可收集，因此无法满足，新增一朵花也无法补充 5 个位置，故输出 -1。

测试用例 6

$b = [9, 8, 7]$，而原序列最大美丽值为 6，即使新增一朵花，最多只能满足其中一个位置的要求（如新增 9 满足 $b_1$），但后续 $b_2=8$ 和 $b_3=7$ 无法通过原序列或新增花满足（原序列无 >=8 和 >=7 的花），因此输出 -1。

测试用例 7

原序列 $[7,7,6,7,7]$ 需收集 5 朵花，$b = [7,7,7,7,7]$。原序列中第 3 朵花的值为 6，不满足 $b_3=7$。新增一朵美丽值为 7 的花，替换第 3 朵的位置（或插入相邻位置），即可让收集的 5 朵花均满足 >=7，因此最小 k 为 7。

注意事项

• 新增的花可以放置在任意位置，包括首尾和中间，不改变原序列其他花的相对顺序。
• 收集花时必须严格从左到右，收集的花的位置必须是递增的（即不能回头收集之前的花）。
• 若无需新增花即可满足要求，输出 0；若新增花后仍无法满足，输出 -1；否则输出最小的 k。