문제 설명
마감 시간이 있는 N개의 작업이 주어졌을 때 가장 이득을 최대화하는 스케줄을 찾아주세요.
입력 설명
첫 줄에는 테스트케이스 T(1<=T<=100)가 주어집니다. 각 테스트케이스마다 첫 줄에는 작업의 개수 N(2<=N<=1,000)이 주어집니다. 그다음 줄에는 마감 시간 D(1<=D<=N/2)와 이득 P(1<=P<=100) 쌍이 N개가 주어집니다. 각 작업의 ID는 1부터 차례로 부여합니다.
출력 설명
각 테스트케이스마다 가장 최적 스케줄을 구성하는 타당 집합 S을 작업 ID의 오름차순으로 출력합니다. 이득이 같은 작업에 경우에는 작업 ID가 작은 것을 우선해야 합니다. 출력할 때 각 작업 ID 사이에는 공백을 하나 추가합니다.
2
4
2 30 1 35 2 25 1 40
7
3 40 1 35 1 30 3 25 1 20 3 15 2 10