#P3593. Control
Control
Control
题目描述
小 x 到达 A 市时,第 名病人的病情严重程度为 。每经过一个时刻,如果还没有救治该病人,病情就增加 。因此在时刻 开始救治该病人,需消耗 点体力。
小 x 从到达的时刻 就可以开始救治,每个时刻最多救治一名病人。救治 名不同的病人后即可停止。
若小 x 带了一瓶超级药水,他可在到达时让任意一名病人服下,将该病人的初始病情 变为 。给药不消耗时间,其病情增长速度不变,也不要求他最先接受救治。求最低的总消耗体力。
输入格式
第一行三个整数 。其中 是病人数, 是需要救治的人数。 表示没有超级药水, 表示有一瓶。
接下来 行,每行两个非负整数 ,依次表示病情每时刻增加的数值和初始值。
输出格式
输出一行一个整数,表示最少需要消耗的体力。
样例
3 3 0
1 0
2 1
3 2
7
数据范围
,。 为非负整数。原题范围段给出的上界为 、。