대출 스케줄링

은행은 어떤 대출 신청을 승인할지 결정해야 합니다. 신청들의 집합 $App$이 있고, 각 신청 $a \in App$에는 승인 마감 시각 $d_a$가 있습니다. 신청 $a$를 승인하면 요청된 대출을 $0 \le t_a \le d_a$를 만족하는 정수 시각 $t_a$에 지급해야 하며, 승인 시 은행은 이익 $p_a$를 얻습니다.

시간은 은행이 모든 신청을 한꺼번에 결정하는 시각 $0$부터 정수 단위로 측정됩니다. 은행은 임의의 한 시각에 최대 $L$건의 대출만 지급할 수 있습니다. 은행의 목표는 오직 이익을 최대화하는 것으로, 승인한 각 대출을 마감 시각 이내의 시간 슬롯(각 시간 단위에는 최대 $L$건의 지급이 가능)에 배정할 수 있다는 조건 아래에서 $\text{profit}(S) = \sum_{a \in S} p_a$를 최대로 하는 부분집합 $S \subseteq App$를 고릅니다. 은행이 얻을 수 있는 최대 이익을 구하세요. 여러 개의 데이터 집합을 입력 텍스트 파일에서 읽어 처리하는 프로그램을 작성하세요.

예를 들어 $L = 1$이고 네 개의 신청 $(p_a, d_a) = (4, 2)$, $(p_b, d_b) = (1, 0)$, $(p_c, d_c) = (2, 0)$, $(p_d, d_d) = (3, 1)$이 있을 때를 생각해 봅시다. 아래 표는 승인 가능한 모든 신청 집합과 대출 지급 일정을 보여 줍니다. 가장 높은 이익은 $9$이며 집합 ${a, c, d}$에 대응합니다. 신청 $c$의 대출은 시각 $0$에, $d$는 시각 $1$에, $a$는 시각 $2$에 지급합니다.

입력에는 여러 개의 데이터 집합이 연달아 주어지며, 파일의 끝에서 종료됩니다. 각 데이터 집합은 두 정수 $N$ ($0 \le N \le 10000$, 신청의 개수)과 $L$ ($0 \le L \le 100$, 은행이 한 시각에 지급할 수 있는 대출의 최대 개수)로 시작합니다. 이어서 $N$개의 정수 쌍 $p_i\ d_i$ ($0 \le p_i \le 10000$, $0 \le d_i \le 10000$)가 주어지며, 각각 신청 $i$의 이익과 마감 시각을 나타냅니다. 입력 데이터는 공백으로 구분되고, 항상 올바르며, 파일의 끝에서 종료됩니다.

각 데이터 집합마다 승인한 신청으로부터 은행이 얻을 수 있는 최대 이익을 표준 출력의 한 줄에 하나씩, 줄 맨 앞부터 출력합니다. 빈 줄은 출력하지 않습니다.