Планування Позики
Банк Північного Полюса має прийняти рішення щодо набору заявок на іпотеку App. Кожна заявка a∈App має крайній термін прийняття d_a, тобто необхідний кредит має бути виплачений у момент часу t_a, де 0≤t_a≤d_a. Якщо заявка прийнята, Банк отримує прибуток p_a. Час вимірюється в цілих одиницях, починаючи з умовного початку часу 0, коли Банк приймає рішення щодо всіх заявок App. Крім того, Банк може виплатити максимум L кредитів у будь-який момент часу. Політика Банку зосереджена виключно на прибутку: він приймає підмножину S⊆App заявок, яка максимізує прибуток. Завдання полягає в обчисленні максимального прибутку, який Банк може отримати з даного набору заявок App на іпотеку.
Наприклад, розглянемо, що L=1, App={a,b,c,d}, (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 і відповідає набору {c,d,a}. Кредит, запитаний у заявці c, виплачується в момент часу 0, кредит, що відповідає d, виплачується в момент часу 1, і, нарешті, кредит a виплачується в момент часу 2.
Вхідні дані
Напишіть програму, яка зчитує набори даних з вхідного текстового файлу. Кожен набір даних відповідає набору заявок на іпотеку і починається з двох цілих чисел: 0≤N≤10000, що показує кількість заявок у наборі, і 0≤L≤100, що показує максимальну кількість кредитів, які Банк може виплатити в будь-який момент часу. Далі йдуть N пар цілих чисел p_i d_i, i=1..N, які вказують прибуток 0≤p_i≤10000 і крайній термін 0≤d_i≤10000 заявки i. Вхідні дані розділені пробілами, є коректними і завершуються кінцем файлу.
Вихідні дані
Для кожного набору даних програма обчислює максимальний прибуток, який Банк може отримати від прийнятих заявок на іпотеку, що відповідають цьому набору даних. Результат виводиться на стандартний вихід з початку рядка. Порожніх рядків у виводі бути не повинно. Приклад вхідних/вихідних даних показано нижче.