Поликарп часто пользуется своим смартфоном. Он уже установил на него \(n\) приложений. Приложение с номером \(i\) занимает \(a_i\) единиц памяти.
Недавно Поликарпу потребовалось установить новое приложение на свой смартфон. Однако, для установки требуется освободить хотя бы \(m\) единиц памяти (удаляя некоторые приложения).
Конечно же, некоторые приложения для Поликарпа важнее, чем другие. Он придумал следующую систему оценки — каждому приложению он сопоставил целое число \(b_i\):
- \(b_i = 1\) — обычное приложение;
- \(b_i = 2\) — важное приложение.
По такой системе оценки, его телефон имеет \(b_1 + b_2 + \ldots + b_n\) очков удобства.
Поликарп считает, что если он удалит приложения с номерами \(i_1, i_2, \ldots, i_k\), то он освободит \(a_{i_1} + a_{i_2} + \ldots + a_{i_k}\) единиц памяти и потеряет \(b_{i_1} + b_{i_2} + \ldots + b_{i_k}\) очков удобства.
Например, если \(n=5\), \(m=7\), \(a=[5, 3, 2, 1, 4]\), \(b=[2, 1, 1, 2, 1]\), то Поликарп может удалить следующие наборы приложений (ниже перечислены не все варианты):
- приложения с номерами \(1, 4\) и \(5\). В таком случае он освободит \(a_1+a_4+a_5=10\) единиц памяти и потеряет \(b_1+b_4+b_5=5\) очков удобства;
- приложения с номерами \(1\) и \(3\). В таком случае он освободит \(a_1+a_3=7\) единиц памяти и потеряет \(b_1+b_3=3\) очков удобства.
- приложения с номерами \(2\) и \(5\). В таком случае он освободит \(a_2+a_5=7\) единиц памяти и потеряет \(b_2+b_5=2\) очков удобства.
Помогите Поликарпу, выберите набор приложений, удалив которые он освободит хотя бы \(m\) единиц памяти и потеряет минимальное количество очков удобства или укажите, что не существует такого набора.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите:
- -1, если не существует набора приложений, удаление которых освободит хотя бы \(m\) единиц памяти;
- минимальное количество очков удобства, которые Поликарп потеряет, если такой набор существует.
Примечание
В первом наборе входных данных оптимально удалить приложения с номерами \(2\) и \(5\), освободив \(7\) единиц памяти. \(b_2+b_5=2\).
Во втором наборе входных данных удалив единственное приложение Поликарп сможет очистить только \(2\) единицы памяти из \(3\) необходимых.
В третьем наборе входных данных оптимально удалить приложения с номерами \(1\), \(2\), \(3\) и \(4\), освободив \(10\) единиц памяти. \(b_1+b_2+b_3+b_4=6\).
В четвертом наборе входных данных оптимально удалить приложения с номерами \(1\), \(3\) и \(4\), освободив \(12\) единиц памяти. \(b_1+b_3+b_4=4\).
В пятом наборе входных данных оптимально удалить приложения с номерами \(1\) и \(2\), освободив \(5\) единиц памяти. \(b_1+b_2=3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 7
5 3 2 1 4
2 1 1 2 1
1 3
2
1
5 10
2 3 2 3 2
1 2 1 2 1
4 10
5 1 3 4
1 2 1 2
4 5
3 2 1 2
2 1 2 1
|
2
-1
6
4
3
|