점검 창에 맞춘 지원 작업

문제

사내 IT 지원팀은 직원들이 업무를 마친 뒤 공용 장비를 점검한다. 오늘 사용할 수 있는 점검 창의 길이는 정확히 T분이다. 지원팀은 이 시간에 실행할 수 있는 독립적인 작업 N개를 준비했으며, 각 작업에 필요한 시간은 미리 측정되어 있다. 작업 시간은 모두 양의 정수이고, 실행 중에 작업을 중단하거나 일부만 실행할 수는 없다. 지원팀은 준비한 작업 중 일부를 골라 하나씩 차례로 실행하려 한다. 각 작업은 최대 한 번만 선택할 수 있다. 서로 다른 작업 사이에는 준비 시간이나 대기 시간이 없으므로, 선택한 작업들의 실행 시간 합이 전체 점검 시간이다. 작업을 실행하는 순서에 따라 시간이 달라지지는 않는다. 실행 시간이 같은 작업이 여러 개 있어도 이들은 서로 다른 작업이므로 각각 한 번씩 선택할 수 있다. 장비의 예약 시스템은 점검 창이 끝나는 순간 모든 작업이 완료되어야 다음 날의 업무 준비를 시작한다. 따라서 선택한 작업 시간의 합은 T보다 작아도 안 되고 커도 안 된다. 작업을 마친 뒤 남는 시간을 기다리는 것으로 채우는 것도 허용되지 않는다. 지원팀은 시간을 정확히 맞추는 선택이 여러 개라면, 확인해야 할 작업 기록을 줄이기 위해 선택한 작업의 수가 가장 적은 것을 사용한다. 예를 들어 시간이 같은 두 작업을 선택한 경우에는 두 작업의 시간을 모두 합하고 작업 수도 2개로 센다. 반대로 시간을 정확히 맞출 방법이 없다면 작업을 시작하지 않는다. 작업 목록과 점검 창의 길이가 주어질 때, 실행 시간이 정확히 T분이 되는 선택에 필요한 최소 작업 수를 구한다. 최소 작업 수가 같은 선택 사이에는 우선순위가 없으며, 선택한 작업의 번호나 실행 순서는 출력하지 않는다.

입력

첫째 줄에 정수 N과 T가 공백으로 주어진다. 둘째 줄에 각 작업의 실행 시간 A_1, A_2, ..., A_N이 공백으로 주어진다.
1 ≤ N ≤ 20
1 ≤ T ≤ 1,000,000
1 ≤ A_i ≤ 1,000,000
입력의 모든 수는 정수이다.

출력

실행 시간의 합이 정확히 T가 되도록 선택할 수 있다면 최소 작업 수를 한 줄에 출력한다. 그러한 선택이 없다면 -1을 출력한다.

6 17
9 8 6 5 4 3

2

4 11
2 4 6 8

-1

3 12
6 6 6

2

출처: Devin.KR 자체 제작