알림을 줄이는 할인권

문제

배달 앱에서 한 이용자가 앞으로 결제할 주문 N건을 모아 관리하고 있다. 각 주문에는 그 주문에서만 쓸 수 있는 할인권이 하나씩 연결되어 있다. i번 주문의 할인권을 적용하면 결제 예정 금액이 정확히 A_i원 줄어든다. 모든 주문의 결제 예정 금액은 해당 할인액 이상이므로, 할인액이 주문 금액 때문에 줄어드는 경우는 없다. 이용자는 할인권을 적용할 때마다 별도의 확인 알림을 받아야 한다. 따라서 전체 결제 예정 금액을 적어도 T원 줄이면서, 확인해야 하는 알림의 수를 최대한 적게 만들고 싶다. 할인권 하나를 적용할 때 발생하는 알림은 정확히 하나다. 할인권은 각각 최대 한 번만 적용할 수 있고, 일부 금액만 나누어 적용할 수는 없다. 할인권 사이에는 추가 조건이 없다. 어느 주문의 할인권을 적용하더라도 다른 주문의 할인권이나 할인액에는 영향을 주지 않는다. 할인권을 적용하는 순서도 결과에 영향을 주지 않으며, 선택한 할인권의 할인액을 모두 더한 값이 전체 감소 금액이 된다. 목표를 정확히 맞출 필요는 없고, 감소 금액이 T원을 넘어도 된다. 예를 들어 목표가 12원이고 선택한 두 할인권의 할인액이 각각 8원과 7원이라면, 전체 감소 금액은 15원이므로 목표를 달성한다. 다만 다른 할인권 하나만으로 목표를 달성할 수 있다면 두 장을 선택한 결과는 최소가 아니다. 목표를 달성하기 위해 적용해야 하는 할인권 개수의 최솟값을 구한다. 같은 최소 개수를 만드는 선택이 여러 개여도 개수만 구한다. T가 0이면 아무 할인권도 적용할 필요가 없다. 모든 할인권을 적용해도 목표에 도달하지 못하면 달성할 수 없다고 판단한다.

입력

첫째 줄에 정수 N과 T가 공백으로 주어진다. 둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 주어진다.
1 ≤ N ≤ 40,000
0 ≤ T ≤ 40,000,000
1 ≤ A_i ≤ 999
모든 금액의 단위는 원이다.

출력

목표를 달성할 수 있으면 필요한 할인권 개수의 최솟값을 정수 하나로 출력한다. 달성할 수 없으면 -1을 출력한다. T가 0이면 0을 출력한다.

6 19
4 9 3 8 5 2

3

3 16
5 5 5

-1

1 0
7

0

출처: Devin.KR 자체 제작