7593: BZOJ3593:Control

Memory Limit:128 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

小x励志当一名医生。某年某月某日,在A市爆发了一场疫情。病毒繁衍地非常快,每个病
人病情的严重程度可以用一个非负整数来衡量。这个城市有n个病人。在小x刚到达这个城市的时
候,每个病人的病情可以用b表示。每过一个时刻,病人的病情会增加a。注意上面所述的a、b对
每一个病人不一定相同。救治一个病情严重程度为x的病人,小x需要消耗x点体力。小x刚到达
这个城市的时候就可以开始救治。
    有些时候,小x会带来一瓶超级药水,在他到达这个城市的时候可以给某个病人服下(不消耗
时间,也不一定要最先救治这个病人),那么这个病人的b值会变成0。
    只要成功救治了p个病人,就可以认为病情稳定,小x就可以休息了。问小x最少需要消耗多少
体力。


输入格式

第一行有3个整数n、p、k,其中n、p的含义如题面。若k为0,则小x没
带超级药水;否则小x带了超级药水。
接下去n行,每行有两个非负整数a、b,表示一个病人的a、b值。


输出格式

仅包含一个整数,表示小x的最小体力花费。


样例输入

3 3 0
1 0
2 1
3 2

样例输出

7

提示

l <= n <= 100000,l <= P<= n,O<k<l,0 < a < 10^7,0 < B <  10^12


题目来源

By xyz111

加入题单

上一题 下一题 算法标签: