PID585 / Blair的小女人
题目描述

光阴似箭,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。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论