마감 전 세탁 묶음

문제

한 세탁소에서는 영업을 마치기 전에 시험용 세탁기를 한 번 가동하려 한다. 이번 시험에서는 세탁물의 총 무게가 정해진 목표 무게와 정확히 같아야 한다. 무게가 부족하거나 넘치는 경우에는 시험 결과를 기록할 수 없다. 세탁소에는 고객별로 포장된 세탁 묶음이 있으며, 각 묶음에는 무게와 추가 처리 비용이 적혀 있다. 세탁 묶음은 포장을 뜯지 않은 상태로 넣어야 하므로 일부만 선택할 수 없다. 각 묶음은 한 번만 사용할 수 있으며, 다른 묶음과 무게나 비용이 같더라도 서로 별개의 묶음이다. 선택하지 않은 묶음은 다음 날 처리하므로 이번 시험의 비용에 포함하지 않는다. 세탁기를 가동하는 기본 비용도 이번 계산에는 포함하지 않는다. 관리자는 목표 무게를 정확히 채우는 모든 선택 중 추가 처리 비용의 합이 가장 작은 선택을 찾으려 한다. 묶음을 입력된 순서대로 고를 필요는 없으며, 선택한 묶음을 세탁기에 넣는 순서도 결과에 영향을 주지 않는다. 무게와 비용은 모두 양의 정수이므로 묶음을 더 선택하면 총 무게와 총 비용이 각각 증가한다. 예를 들어 목표 무게보다 가벼운 묶음만 남아 있더라도 여러 묶음의 합으로 목표를 채울 수 있다. 반대로 전체 묶음의 무게 합이 충분하다는 사실만으로 목표를 정확히 채울 수 있는 것은 아니다. 따라서 사용할 묶음의 조합을 살펴보아야 한다. 목표 무게를 만드는 선택이 여러 개이고 최소 비용도 같다면 어느 선택을 사용해도 된다. 이 문제에서는 선택한 묶음의 번호를 출력하지 않고 최소 비용만 출력한다. 어떤 선택으로도 목표 무게를 만들 수 없다면 -1을 출력한다.

입력

첫째 줄에 묶음 수 N과 목표 무게 T가 공백으로 주어진다. 1 ≤ N ≤ 18, 1 ≤ T ≤ 1,000이다.
다음 N개 줄에는 각 묶음의 무게 W와 추가 처리 비용 C가 공백으로 주어진다. 1 ≤ W ≤ 1,000, 1 ≤ C ≤ 1,000,000이다.
입력에 등장하는 모든 수는 정수이다.

출력

목표 무게를 정확히 만드는 선택의 최소 추가 처리 비용을 정수 하나로 출력한다. 가능한 선택이 없으면 -1을 출력한다.

4 7
3 8
4 9
7 25
2 1

17

3 5
2 3
4 1
6 2

-1

3 4
4 10
2 3
2 3

6

출처: Devin.KR 자체 제작