光阴似箭，ROIP（Renqing Olympiad in Informatics In Provinces）快到了，然而更重要的是，Blair的春天也来了^^。因为Blair有小女人，eg，yh。 所以，Blair总是抛弃信息学的同僚，陪着yh吃饭。

说到超二（超级二中）这个学校，那可是一大人口聚集地，人口密度远超过maxlongint。学校的饭有许多菜系，eg：川菜系、粤菜系等等。Blair有一无法违反的伴有强迫症的菜单，把所有的日子划成每多少多少天为某菜系专吃时间段，因为Blair认为这样才有目标，要不然在跑饭大军中Blair和yh就什么都吃不到了。= =！

在伟大的Blair特色哲学主义定理光辉的引导下，Blair&&yh每天都能跑到饭，但是很快Blair发现，发现……“我小女人总赖上一种菜系呢……好懒T_T”，也就是说，如果Blair今天带着yh吃了川菜系，那么Blair强行要求改变yh的菜系指向之前，yh将一直赖着吃川菜。

也许，你觉得这和Blair的菜系专吃时间段是天造地设的事啊！但是，由于强行改变yh的菜系指向会使得yh不开心，Blair总共需要陪着yh吃n个菜系专吃时间段的饭，他只能在某个菜系专吃时间段的第一天（Twist：强迫症的表现……）强行改变恰好m次yh的菜系指向。所以，Blair委曲求全，打算将某几个菜系专吃时间段整个合并为一个菜系专吃时间段，为第一种菜系的菜系专吃时间段，最终将n个菜系专吃时间段合并成m+1个。

于是，一个问题出现了：第i个菜系专吃时间段的长度为Li天，并且如果吃该菜系，一天会增加yh对Blair的好感度Ei。

Eg，若Blair共有4个菜系专吃时间段，只能强行改变1次yh的菜系指向：

最终，yh的Blair好感度会飞涨139，如果不改变的话，只会增加76。（Twist：终于发现Blair委曲求全的原因了，这哪里委曲了……）

现在，你需要帮助因为正在看yh照片傻笑而没有空闲时间的Blair算一算他利用这n个菜系专吃时间段能讨得yh的好感度和的最小值ANS，以防止yh发现Blair他想要＃&*（*&＃｝……f*&@&* “）：……%……的不良真相……= =！

数据范围：

对于100%的数据，N<=1000,M<=100

数据中的任意整数不超过1000

第1行，为两个整数N和M，即菜系专吃时间段的数目和改变yh菜系指向的次数。

以下N行，每行两个整数Li和Ei，分别表示时间顺序的第i菜系专吃时间段的长度和每天能增加的好感度。

一行，ANS。