题目描述

北极海滩银行需要审批一组抵押贷款申请（记为集合 App）。每个申请 a ∈ App 包含一个批准截止时间 da，即该笔贷款必须在时间 ta（0 ≤ ta ≤ da）之前发放。若申请被批准，银行将获得利润 pa。时间以整数单位计算，从基准时刻 0 开始（此时银行需对所有申请作出决策）。此外，银行在任意时刻最多只能发放 L 笔贷款。银行的策略仅关注利润最大化：它需要选择一个申请子集 S ⊆ App，使得总利润最大。问题要求计算银行从给定申请集合 App 中能获得的最大利润。

例如，假设 L = 1，App = {a, b, c, d}，其中 (pa, da) = (4,2)、(pb, db) = (1,0)、(pc, dc) = (2,0)、(pd, dd) = (3,1)。下表展示了所有可能的批准组合及贷款发放时间安排。最高利润为 9，对应子集 {c, d, a}：申请 c 的贷款在时间 0 发放，d 在时间 1 发放，a 在时间 2 发放。

输入

程序需从文本文件中读取多组数据。每组数据对应一组抵押贷款申请，以两个整数开头：

• 0 ≤ N ≤ 10000，表示申请数量；
• 0 ≤ L ≤ 100，表示银行任意时刻最多可发放的贷款数。
  随后是 N 对整数 pi di（i=1..N），分别表示第 i 个申请的利润 0 ≤ pi ≤ 10000 和截止时间 0 ≤ di ≤ 10000。输入数据由空格分隔，保证正确性，并以文件结束符终止。

输出

对每组数据，程序需计算银行通过批准相应申请能获得的最大利润。结果从行首开始输出，且不得包含空行。输入/输出示例如下：

输入数据 1

4 1     4 2  1 0   2 0    3 1

7 2
200 1   200 1   100 0   1000 2    80 1
50 20   500 1

0 100

1 0     4 1000

输出数据 1

9
2050
0
0