Это простая версия задачи. Единственное отличие заключается в том, что в этой версии вам нужно вывести только минимальную суммарную стоимость операций. Вы можете делать взломы, только если обе версии задачи решены.
Даны массив \(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\). В противном случае выведите минимальную суммарную стоимость операций.
Выходные данные
Для каждого набора входных данных, если возможно сделать \(a\) пустым, выведите минимальную суммарную стоимость операций.
Если не существует последовательности операций, которая делает \(a\) пустым, то выведите одно число \(-1\).
Примечание
В первом наборе входных данных оптимальная последовательность операций, имеющая стоимость \(1\), выглядит следующим образом:
- Выполните операцию типа \(2\). Выберите префикс \([9]\). Эта операция стоит \(1\).
- Выполните операцию типа \(1\). Значение \(k\) теперь равно \(2\). Это не влечет за собой никаких затрат.
- Выполните операцию типа \(2\). Выберите префикс \([3, 4]\). Эта операция стоит \(0\).
- Выполните операцию типа \(2\). Выберите префикс \([3]\). Эта операция стоит \(0\).
- Массив \(a\) стал пустым, а суммарная стоимость всех операций равна \(1\).
Во втором наборе входных данных невозможно удалить ни одного префикса массива, так как \(a_1 > b_1\), поэтому массив \(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
|