花童有一个由 $$$n$$$ 花组成的花园,可以表示为整数序列 $$$a_1, a_2, \dots, a_n$$$,其中 $$$a_i$$$ 是从左边算起第 $$$i$$$ 朵花的美丽程度。
Igor 想要收集恰好 $$$m$$$ 的花。为此,他将在花园里散步 从左到右 并选择是否在当前位置采集花朵。他收集的第 $$$i$$$ 朵花一定很美 至少 $$$b_i$$$。
Igor 注意到可能无法收集到满足他的美丽要求的 $$$m$$$ 鲜花,所以 之前 他开始收集鲜花,他可以选择任何整数$$$k$$$并使用他的魔杖种植一朵美丽的新花$$$k$$$并将其放置 任何地方 在花园里(两朵花之间、第一朵花之前或最后一朵花之后)。因为他的魔法能力有限,他可能会这么做 最多一次.
输出 最小值 整数$$$k$$$ Igor在执行上述操作时必须选择,以确保他可以收集$$$m$$$花。如果他可以在不使用操作的情况下收集$$$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, ..., a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — 其中 $$$a_i$$$ 是花园中从左边算起第 $$$i$$$ 朵花的美丽程度。
每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, b_2, ..., b_m$$$ $$$(1 \le b_i \le 10^9)$$$ - 其中 $$$b_i$$$ 是 Igor 将收集的第 $$$i$$$ 朵花必须具有的最小美度。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上输出 Igor 在执行上述操作时必须选择的最小整数 $$$k$$$,以确保他可以收集 $$$m$$$ 花。如果他可以在不使用操作的情况下收集$$$m$$$朵花,则输出$$$0$$$。如果使用该操作仍无法收集$$$m$$$花,则输出$$$-1$$$。
示例
输入复制
79 53 5 2 3 3 5 8 1 24 6 2 4 66 31 2 6 8 2 15 4 35 34 3 5 4 37 4 56 38 4 2 1 2 56 1 45 51 2 3 4 55 4 3 2 16 31 2 3 4 5 69 8 75 57 7 6 7 77 7 7 7 7
输出复制
6 3 7 0 -1 -1 7
注意
在第一个测试用例中,假设 Igor 种了一朵美丽的花 $$$6$$$ 并将其放置在第三朵和第四朵花之间。然后,花园将如下所示:$$$[3, 5, 2, 6, 3, 3, 5, 8, 1, 2]$$$。然后,他可以选择第二、第四、第六、第七和第八朵花,其中有美女$$$[5,6,3,5,8]$$$。
在第三个测试用例中,他可以种植一朵美丽的花 $$$7$$$ 并将其放置在第一朵花之前。花园将如下所示:$$$[7, 4, 3, 5, 4, 3]$$$。现在,他可以选择第一朵、第二朵、第四朵花。
在第四个测试用例中,Igor不需要使用该操作,因此答案是$$$0$$$。
在第六个测试用例中,无论 Igor 如何执行操作,他都无法收集到 $$$3$$$ 朵花,使得他收集到的第 $$$i$$$ 朵花的美度至少为 $$$b_i$$$,因此答案为 $$$-1$$$。