33259번 - 상현이의 수강신청 대작전 스페셜 저지

문제

KSA에서는 자신이 수강하고 싶은 과목을 골라 수강신청을 해야한다. 상현이는 총 학점이 $M$학점 초과가 되도록 신청하면 도저히 GPA를 유지할 수 없을 것 같아 $M$학점 이하로 과목들을 골라 신청하고자 한다. 수강신청 가능한 과목은 총 $N$개이며, 1ドル$부터 $N$까지의 번호가 붙여져 있다. $i$번 과목에 대한 상현이의 선호도는 $P_i$이고, 학점은 $C_i$이다. 이때 총 학점이 $M$학점 이하면서 선호도의 총합이 최대화되도록 수강신청을 하는 방법을 구하는 프로그램을 작성하시오. (단, 각 과목은 최대 한 번씩만 선택할 수 있으며, 최소 한 과목 이상을 신청해야 한다.)

입력

첫 번째 줄에 두 개의 정수 $N$$(1 \le N \le 5000)$과 $M$$(1 \le M \le 5000)$이 주어진다.

다음의 $N$개의 줄 중 $i$번째 줄에 두 개의 정수 $P_i$$(1 \le P_i \le 10^5)$와 $C_i$$(1 \le C_i \le 5000)$이 주어진다.

출력

첫 번째 줄에 문제의 조건에 따라 수강신청을 하는 방법이 존재한다면 신청할 과목의 수를 출력하고, 아니라면 $-1$을 출력한다.

만약 그러한 방법이 존재한다면, 두 번째 줄에 신청할 과목의 번호들을 오름차순으로 출력한다.

정답이 여러 개 존재한다면 그중 아무거나 출력해도 상관없다.

제한

힌트