题目描述

货运站来了一批箱子，不同的箱子装有不同价值的货物，你需要将箱子装在卡车上，假设一辆卡车能装载m个箱子，聪明的你想一想，如何装箱，才能使卡车的货物价值最大？

输入格式

第1行两个整数n,m，分别表示箱子的种类和卡车所能装载箱子的数量。 第2~n+1行，每行两个数字，分别表示某种箱子的数量和箱子中货物的价值。

输出格式

1行一个整数，表示货物的最大价值。

3 4
1 3
2 2
3 1

8

数据规模

1 <= n, m <= 10000