结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

程老师经营一间冷库，专门做蔬果批发的生意。这一批货他进了 $n$ 种商品，每种商品只有一件，商品按 $1 \sim n$ 编号。冷库从入库当天开始出货：第 $1$ 天是能出货的第一天，这批货能安排的日子就是第 $1$ 天到第 $n$ 天，一天一天往下排，没有更晚的档期。第 $i$ 种商品的保质期是 $d_i$ 天，意思是它在第 $1$ 天到第 $d_i$ 天之间都能拿出来卖，第 $d_i$ 天是它还能卖的最后一天，过了这一天就报废，只能丢掉。

冷库每天只开一次出货口。这一趟最多能装走 $k$ 件商品，装几件都可以，但至多 $k$ 件，装不下就得留到后面再安排。一件商品只会卖出一次，卖出它的那一天不能晚于它的保质期。第 $i$ 种商品卖出去一件，程老师能赚 $v_i$ 元。

请替程老师把这批货的出货档期排出来：每种商品分别在哪一天卖出，或者干脆不卖报废掉，使得这批货赚到的总金额最大。你只需要告诉他这个最大的总金额。

输入格式

从文件 stock.in 中读入数据。

• 第一行两个整数 $n, k$，依次表示商品的种数与每天出货的件数上限；
• 接下来 $n$ 行，第 $i$ 行两个整数 $d_i, v_i$，依次表示第 $i$ 种商品的保质期天数与卖出一件能赚到的金额。

输出格式

输出到文件 stock.out 中。

一行一个整数，表示这批货能赚到的最大总金额。

样例

4 2
2 50
1 20
2 30
1 10

110

样例 1 解释

这批货共 $4$ 种商品，每天最多出 $2$ 件。保质期只有 $1$ 天的是利润 $20$ 和利润 $10$ 这两件，它们只能在第 $1$ 天卖，第 $2$ 天就已经报废了；第 $1$ 天恰好能装 $2$ 件，把这两件都排上。剩下两种保质期为 $2$ 天的商品（利润 $50$ 与 $30$）排在第 $2$ 天。这样 $4$ 件商品全部卖出，总金额为 $20 + 10 + 50 + 30 = 110$。而这批货全部商品的利润之和就是 $110$，不可能再多。

3 1
1 100
1 50
2 60

160

样例 2 解释

每天最多出 $1$ 件。第 $1$ 天能卖的只有保质期为 $1$ 天的那两件，货口这一趟只装得下 $1$ 件，取利润更大的 $100$ 那件。第 $2$ 天卖保质期为 $2$ 天的那件，得 $60$。利润 $50$ 的那件在第 $1$ 天没排上，第 $2$ 天已经过了保质期，只能报废。总金额为 $100 + 60 = 160$。如果第 $1$ 天改卖 $50$ 那件，第 $2$ 天仍然只装得下 $1$ 件（$60$ 那件），总金额只有 $110$，比 $160$ 低。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，$1 \le k \le 10$；
• $1 \le d_i \le n$，$1 \le v_i \le 10^4$；
• 每种商品只有一件。

各测试点的约束如下：

• 特殊性质 A：$k = 1$；
• 特殊性质 B：所有 $d_i = n$。