当前没有测试数据。

题目描述

小明是一位勇敢的探险家，他听说在一座神秘的山洞中散落着 $N$ 颗珍贵的能量石。小明准备出发去收集这些能量石，但收集过程有一些特殊的规则需要遵守。

山洞中的能量石排成一条直线，从左到右编号为 $1$ 到 $N$。每颗能量石都有一个种类 $T_i$（用一个整数表示）和能量值 $V_i$。小明必须按照编号从小到大的顺序依次经过每颗能量石，并决定是否收集它。

收集规则如下：

• 小明最多只能收集 $K$ 颗能量石。
• 如果小明选择收集某颗能量石，他将获得该能量石的能量值。
• 但是，如果小明已经收集了两颗与当前能量石种类相同的能量石，那么他不能再收集当前这颗能量石。

你的任务是帮助小明计算出，在遵守所有规则的前提下，他能够收集到的能量石的总能量值最大是多少？

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示能量石的数量和小明最多能收集的能量石数量。

接下来 $N$ 行，每行包含两个整数 $T_i$ 和 $V_i$，表示第 $i$ 颗能量石的种类和能量值。

输出格式

输出一个整数，表示小明能够收集到的能量石的最大总能量值。

样例 #1

输入

5 3
1 10
2 20
1 30
3 40
2 50

输出

100

样例 #2

输入

7 4
1 15
1 25
2 10
3 20
2 30
1 35
4 5

输出

95

样例说明

样例 1 解释

最优方案是收集第 2 颗（能量值 20）、第 3 颗（能量值 30）、第 5 颗（能量值 50），总能量值为 $20+30+50=100$。

数据范围

对于 $30\%$ 的数据，$1 \le N \le 100$，$1 \le K \le 10$。

对于 $100\%$ 的数据，$1 \le N \le 100$，$1 \le K \le 50$，$1 \le T_i \le 100$，$1 \le V_i \le 1000$。