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

Это простая версия задачи. Единственное отличие заключается в том, что в этой версии вам нужно вывести только минимальную суммарную стоимость операций. Вы можете делать взломы, только если обе версии задачи решены.

Даны массив $$$a$$$ длины $$$n$$$ и массив $$$b$$$ длины $$$m$$$ ($$$b_i > b_{i+1}$$$ для всех $$$1 \le i < m$$$). Изначально значение $$$k$$$ равно $$$1$$$. Ваша цель — сделать массив $$$a$$$ пустым, выполняя операции двух типов:

  • $$$1$$$ тип: Если значение $$$k$$$ меньше $$$m$$$ и массив $$$a$$$ не пуст, вы можете увеличить значение $$$k$$$ на $$$1$$$. Это не влечет за собой никаких затрат.
  • $$$2$$$ тип: Удалить непустой префикс массива $$$a$$$, такой, что его сумма не превосходит $$$b_k$$$. Стоимость этой операции равна $$$m - k$$$.

Вам нужно минимизировать суммарную стоимость последовательности операций, в результате которой массив $$$a$$$ станет пустым. Если сделать массив пустым невозможно, выведите $$$-1$$$. В противном случае выведите минимальную суммарную стоимость операций.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$, $$$\boldsymbol{1 \le n \cdot m \le 3 \cdot 10^5}$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Третья строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le 10^9$$$). Гарантируется, что $$$b_i > b_{i+1}$$$ для всех $$$1 \le i < m$$$.

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

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

Для каждого набора входных данных, если возможно сделать $$$a$$$ пустым, выведите минимальную суммарную стоимость операций.

Если не существует последовательности операций, которая делает $$$a$$$ пустым, то выведите одно число $$$-1$$$.

Пример
Входные данные
5
4 2
9 3 4 3
11 7
1 2
20
19 18
10 2
2 5 2 1 10 3 2 9 9 6
17 9
10 11
2 2 2 2 2 2 2 2 2 2
20 18 16 14 12 10 8 6 4 2 1
1 6
10
32 16 8 4 2 1
Выходные данные
1
-1
2
10
4
Примечание

В первом наборе входных данных оптимальная последовательность операций, имеющая стоимость $$$1$$$, выглядит следующим образом:

  • Выполните операцию типа $$$2$$$. Выберите префикс $$$[9]$$$. Эта операция стоит $$$1$$$.
  • Выполните операцию типа $$$1$$$. Значение $$$k$$$ теперь равно $$$2$$$. Это не влечет за собой никаких затрат.
  • Выполните операцию типа $$$2$$$. Выберите префикс $$$[3, 4]$$$. Эта операция стоит $$$0$$$.
  • Выполните операцию типа $$$2$$$. Выберите префикс $$$[3]$$$. Эта операция стоит $$$0$$$.
  • Массив $$$a$$$ стал пустым, а суммарная стоимость всех операций равна $$$1$$$.

Во втором наборе входных данных невозможно удалить ни одного префикса массива, так как $$$a_1 > b_1$$$, поэтому массив $$$a$$$ нельзя сделать пустым ни одной последовательностью операций.