C1971 美队的生日

内存限制:256 MB 时间限制:1000 ms

题目描述

灭霸被消灭后,我们最敬爱的美国队长88岁生日即将到来,在生日那天他的朋友们送来很多蛋糕。作为贪吃的美国队长,他认为蛋糕这么好吃的东西一定要多吃。(快赶上雷神了,哈哈)

毕竟美队已经上了年纪,“三高”也紧随他的步伐,为了他的身体着想,他的朋友们决定只允许他吃$$k$$块蛋糕。其中每块蛋糕有它的种类和重量。

美队为了吃更多的口味的蛋糕,他决定每个种类蛋糕只取一块,但是他太喜欢蛋糕了,所以他希望你可以帮他算出吃最多蛋糕重量的总和。

H图片.jpg

输入格式

第1行输入两个整数$n,k$。其中$n$代表有$n$个蛋糕,$k$代表只能吃$k$块。$(0 \le n \le 1000,0 \le k \le 1000)$。

接下来每行输入两个整数 $v,w$ 。其中 $v$ 代表蛋糕的种类,$w$ 代表蛋糕的重量。$(0 \le v \le n,1 \le w \le 10^5)$。

输出

输出一个整数,代表吃下最多蛋糕重量的总和。

样例

样例输入 1

5 3 1 1 2 1 2 2 3 4 4 2

样例输出 1

8

提示