D. Цветочный мальчик
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У цветочного мальчика есть сад из $$$n$$$ цветов, которые можно представить в виде последовательности целых чисел $$$a_1, a_2, \dots, a_n$$$, где $$$a_i$$$ — это красота $$$i$$$-го цветка слева.

Игорь хочет собрать ровно $$$m$$$ цветов. Для этого он будет проходить по саду слева направо и выбирать, собирать ли цветок на текущей позиции. Среди собранных цветов, $$$i$$$-й цветок должен иметь красоту не менее $$$b_i$$$.

Игорь заметил, что может быть невозможно собрать $$$m$$$ цветов, которые соответствуют его требованиям по красоте, поэтому перед тем, как он начнет собирать цветы, он может выбрать любое целое число $$$k$$$ и с помощью своей волшебной палочки вырастить новый цветок с красотой $$$k$$$ и разместить его в любом месте в саду (между двумя соседними цветами, перед первым цветком или после последнего цветка). Поскольку его магические способности ограничены, он может сделать это не более одного раза.

Выведите минимальное целое число $$$k$$$, которое Игорь должен выбрать, когда он выполняет вышеупомянутую операцию, чтобы гарантировать, что он сможет собрать $$$m$$$ цветов. Если он может собрать $$$m$$$ цветов без использования операции, выведите $$$0$$$. Если собрать $$$m$$$ цветов невозможно, даже используя операцию, выведите $$$-1$$$.

Входные данные

Первая строка ввода содержит одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных.

Первая строка каждого набора содержит ровно два целых числа $$$n$$$ и $$$m$$$ $$$(1 \le m \le n \le 2 \cdot 10^5)$$$ — количество цветов в саду и количество цветов, которые Игорь хочет собрать, соответственно.

Вторая строка каждого набора содержит $$$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$$$ — это минимальная красота, которую должен иметь $$$i$$$-й цветок, который Игорь соберет.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное целое число $$$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
Примечание

В первом примере предположим, что Игорь вырастит цветок с красотой $$$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$$$.