빈틈없는 운동 시간

문제

한 헬스장은 예약한 운동 시간을 정확히 채우는 개인 운동표를 제공한다. 담당자는 회원에게 제안할 수 있는 운동 항목을 N개 준비했다. 각 항목에는 필요한 시간과 운동 효과 점수가 정수로 적혀 있다. 회원은 이 항목 중 일부를 골라 운동표를 만들며, 선택한 항목의 효과 점수를 모두 더한 값을 운동표의 점수로 사용한다. 각 항목은 한 번만 선택할 수 있다. 이름이 비슷하거나 소요 시간과 효과 점수가 모두 같은 항목이 있어도, 입력에서 서로 다른 줄에 주어졌다면 별개의 항목이다. 항목 사이의 준비와 이동에는 시간이 들지 않는다. 선택한 항목을 실행하는 순서도 총시간과 점수에 영향을 주지 않는다. 따라서 같은 항목들을 순서만 바꾸어 배치한 운동표는 같은 선택으로 취급한다. 이번 예약의 운동 시간은 정확히 T분이다. 헬스장은 예약이 끝나기 전에 운동을 마치고 기다리거나, 예약 시간을 넘겨 운동하는 것을 허용하지 않는다. 그러므로 선택한 항목의 소요 시간 합이 T와 정확히 같아야 한다. 각 항목의 소요 시간은 양의 정수이며 T도 양의 정수이므로, 아무 항목도 선택하지 않은 운동표는 조건을 만족하지 않는다. 담당자는 가능한 운동표 중 효과 점수가 가장 큰 운동표를 찾으려 한다. 사용한 항목의 개수가 적다고 해서 더 좋은 운동표가 되는 것은 아니다. 점수가 같은 운동표가 여러 개라면 어느 것을 골라도 되며, 출력에는 선택한 항목이나 그 순서를 포함하지 않는다. 시간이 정확히 맞는 운동표가 하나도 없을 수도 있다. 모든 항목의 정보와 예약 시간이 주어졌을 때, 조건을 만족하는 최대 점수를 구하거나 가능한 운동표가 없다는 사실을 보고해야 한다.

입력

첫째 줄에 항목의 개수 N과 예약 시간 T가 공백으로 구분되어 주어진다. 다음 N개 줄에 각 항목의 소요 시간 a와 효과 점수 b가 공백으로 구분되어 주어진다. 모든 수는 정수이며 1≤N≤20, 1≤T≤1000000, 1≤a≤1000000, 1≤b≤1000000이다.

출력

소요 시간 합이 정확히 T인 선택의 최대 효과 점수를 출력한다. 그러한 선택이 없으면 -1을 출력한다. 최대 점수가 같은 선택이 여러 개여도 그 점수를 한 번만 출력한다.

5 12
4 8
8 11
6 14
6 13
3 20

27

3 7
2 9
4 12
8 30

-1

4 5
5 7
5 7
2 3
3 4

7

출처: Devin.KR 자체 제작