У Ивана на телефоне есть \(n\) песен. Размер \(i\)-й песни \(a_i\) байт. У Ивана также есть флеш-карта, которая может хранить не более \(m\) байт информации. Изначально его флеш-карта пустая.
Иван хочет записать все \(n\) песен на свою флеш-карту. Он может сжимать некоторые из них. Если он сжимает \(i\)-ю песню, размер \(i\)-й песни уменьшается с \(a_i\) до \(b_i\) байт (\(b_i < a_i\)).
Иван может сжать любое подмножество песен (возможно, пустое) и записать все песни на флеш-карту, если сумма их размеров не превышает \(m\). Он может сжимать любое подмножество песен (не обязательно подряд идущих).
Иван хочет найти минимальное количество песен, которое необходимо сжать, чтобы все песни поместились на флеш-карте (то есть сумма их размеров была меньше либо равна \(m\)).
Если невозможно записать все песни (даже если Иван сожмет все песни, которые у него есть), выведите «-1». Иначе выведите минимальное количество песен, которое Ивану необходимо сжать.
Выходные данные
Если невозможно сжать подмножество песен таким образом, что все песни поместятся на флеш-карту, выведите «-1». Иначе выведите минимальное количество песен, которое необходимо сжать.
Примечание
В первом тестовом примере Иван может сжать первую и третью песни, после этого сумма размеров будет равна \(8 + 7 + 1 + 5 = 21 \le 21\). Также Иван может сжать первую и вторую песни, тогда сумма размеров будет равна \(8 + 4 + 3 + 5 = 20 \le 21\). Заметьте, что сжатия какой-либо одной песни недостаточно, чтобы записать все песни на флеш-карту (например, после сжатия второй песни сумма размеров будет равна \(10 + 4 + 3 + 5 = 22 > 21\)).
Во втором тестовом примере даже если Иван сожмет все песни, сумма размеров будет равна \(8 + 4 + 1 + 4 = 17 > 16\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 21
10 8
7 4
3 1
5 4
|
2
|
|
2
|
4 16
10 8
7 4
3 1
5 4
|
-1
|