Loan Scheduling#792
The North Pole Beach Bank must decide on a set of mortgage applications. Each application i \in A has an acceptance deadline d_i, i.e., the required loan must be paid at time t_i, where 0 \leq t_i \leq d_i. If the application is accepted, the Bank receives a profit p_i. Time is measured in integer units starting from the conventional origin , when the Bank decides upon all the applications. Furthermore, the Bank can pay a maximum of loans at any given time. The Bank's policy is solely focused on profit: it accepts a subset S \subseteq A of applications that maximizes profit. The problem is to compute the maximum profit the Bank can achieve from the given set of mortgage applications.
For example, suppose L = 1, A = \{a, b, c, d\}, (p_a, d_a) = (4, 2), (p_b, d_b) = (1, 0), (p_c, d_c) = (2, 0), and (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 and corresponds to the set \{c, d, a\}. The loan for application is paid at time , the loan for is paid at time , and finally, the loan for is paid at time .
Write a program that reads sets of data from an input text file. Each data set corresponds to a set of mortgage applications and starts with two integers: 0 \leq N \leq 10000 which specifies the number of applications in the set, and 0 \leq L \leq 100 which is the maximum number of loans the Bank can pay at any given time. Following this are pairs of integers p_i d_i, i = 1\ldots N, where 0 \leq p_i \leq 10000 and 0 \leq d_i \leq 10000 specify the profit and deadline of application , respectively. Input data are separated by spaces, are valid, and terminate with end of file.
For each data set, the program calculates the maximum profit the Bank can achieve from the selected set of mortgage applications. The result for each data set should be printed on a new line at the beginning of the line. There should be no blank lines in the output. An example of input/output is shown below.
Example 1