Олимпиадный тренинг

Задача . E. Запросы на поедание конфет


У Тимура есть \(n\) конфет. В \(i\)-й конфете количество сахара равно \(a_i\). Так, съев \(i\)-ю конфету, Тимур потребляет количество сахара, равное \(a_i\).

Тимур задаст вам \(q\) запросов о своих конфетах. Для \(j\)-го запроса вы должны ответить, какое минимальное количество конфет ему нужно съесть, чтобы потребить количество сахара, большее или равное \(x_j\). Выведите -1, если невозможно получить такое количество. Другими словами, нужно вывести минимально возможное \(k\) такое, что, съев \(k\) конфет, Тимур получит количество сахара не менее \(x_j\), или сказать, что такого \(k\) не существует.

Обратите внимание, что он не может съесть одну и ту же конфету дважды, а запросы не зависят друг от друга (Тимур может использовать одну и ту же конфету в разных запросах).

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

Первая строка содержит единственное целое число \(t\) (\(1 \leq t \leq 1000\))  — количество наборов входных данных. Далее следуют описания наборов.

Первая строка каждого набора содержит \(2\) целых числа \(n\) и \(q\) (\(1 \leq n, q \leq 1.5\cdot10^5\)) — количество конфет, которые есть у Тимура и количество запросов соответственно.

Вторая строка каждого набора содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^4\)) — количество сахара в каждой конфете соответственно.

Затем следуют \(q\) строк.

Каждая из \(q\) содержит единственное целое число \(x_j\) (\(1 \leq x_j \leq 2 \cdot 10^9\)) — количество сахара, которое хочет получить Тимур.

Гарантируется, что сумма \(n\) и сумма \(q\) по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

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

Для каждого набора входных данных выведите \(q\) строк. В \(j\)-й строке выведите количество конфет, которое нужно съесть Тимуру, чтобы получить количество сахара, большее или равное \(x_j\). Выведите -1, если получить такое количество невозможно.

Примечание

В первом наборе входных данных примера:

  • В первом запросе Тимур может съесть любую конфету, и он наберет нужное количество.
  • Во втором запросе Тимур может получить количество не менее \(10\), съев \(7\)-ю и \(8\)-ю конфету, таким образом потребив количество сахара, равное \(14\).
  • На третий запрос нет возможного ответа.
  • В четвертом запросе Тимур может получить количество как минимум \(14\), съев \(7\)-ю и \(8\)-ю конфету, таким образом потребив количество сахара, равное \(14\).

Во втором наборе входных данных примера:

  • Для единственного запроса второго набора входных данных мы можем выбрать третью конфету, из которой Тимур получает количество сахара равное \(3\). Также можно получить тот же ответ, выбрав четвертую конфету.

Примеры
№Входные данныеВыходные данные
1
3
8 7
4 3 3 1 1 4 5 9
1
10
50
14
15
22
30
4 1
1 2 3 4
3
1 2
5
4
6
1
2
-1
2
3
4
8
1
1
-1
Статистика успешных решений по компиляторам
 Кол-во
С++5