Loan Scheduling

A bank must decide which mortgage applications to accept. There is a set $App$ of applications, and each application $a \in App$ has an acceptance deadline $d_a$: if it is accepted, the requested loan must be paid at some integer time $t_a$ with $0 \le t_a \le d_a$. Accepting application $a$ gives the bank a profit $p_a$.

Time is measured in integral units starting from time $0$, the moment the bank decides on all applications at once. At any given time the bank can pay at most $L$ loans. The bank cares only about profit: subject to being able to assign every accepted loan to a time slot no later than its deadline (each time unit holds at most $L$ payments), it chooses a subset $S \subseteq App$ that maximizes $\text{profit}(S) = \sum_{a \in S} p_a$. Compute the maximum profit the bank can obtain. Write a program that reads sets of data from an input text file.

For example, consider $L = 1$ and four applications $(p_a, d_a) = (4, 2)$, $(p_b, d_b) = (1, 0)$, $(p_c, d_c) = (2, 0)$, $(p_d, d_d) = (3, 1)$. The table below shows all possible sets of accepted applications and the scheduling of the loan payments. The highest profit is $9$ and corresponds to the set $\{a, c, d\}$: the loan for $c$ is paid at time $0$, the loan for $d$ at time $1$, and the loan for $a$ at time $2$.

The input contains several data sets, one after another, and ends at end of file. Each data set begins with two integers $N$ ($0 \le N \le 10000$, the number of applications) and $L$ ($0 \le L \le 100$, the maximum number of loans the bank can pay at any given time). Then follow $N$ pairs of integers $p_i\ d_i$ ($0 \le p_i \le 10000$, $0 \le d_i \le 10000$) giving the profit and the deadline of application $i$. The input data are separated by white space, are correct, and terminate with an end of file.

For each data set, print on standard output, on its own line and starting at the beginning of the line, the maximum profit the bank can obtain from the accepted applications. There must be no empty lines in the output.