← 返回题目列表

Codeforces · 2106/D

D. 花美男

中文机器翻译题面 查看原题

花童有一个由 $$$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$$$。

示例

输入
复制

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

注意

在第一个测试用例中,假设 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$$$。