#P3593. Control

    ID: 2800 传统题 2000ms 128MiB 尝试: 165 已通过: 23 难度: 10 上传者: 标签>难度分类省选/NOI-贪心排序贪心交换论证动态规划线性 DP构造与建模差分转化数据结构FHQ Treap 分裂合并按排名分裂排序与序列处理二分查找有限候选集缩减CF2900Byxyz111

Control

Control

题目描述

小 x 到达 A 市时,第 ii 名病人的病情严重程度为 bib_i。每经过一个时刻,如果还没有救治该病人,病情就增加 aia_i。因此在时刻 tt 开始救治该病人,需消耗 bi+taib_i+t a_i 点体力。

小 x 从到达的时刻 00 就可以开始救治,每个时刻最多救治一名病人。救治 pp 名不同的病人后即可停止。

若小 x 带了一瓶超级药水,他可在到达时让任意一名病人服下,将该病人的初始病情 bib_i 变为 00。给药不消耗时间,其病情增长速度不变,也不要求他最先接受救治。求最低的总消耗体力。

输入格式

第一行三个整数 n,p,kn,p,k。其中 nn 是病人数,pp 是需要救治的人数。k=0k=0 表示没有超级药水,k=1k=1 表示有一瓶。

接下来 nn 行,每行两个非负整数 ai,bia_i,b_i,依次表示病情每时刻增加的数值和初始值。

输出格式

输出一行一个整数,表示最少需要消耗的体力。

样例

3 3 0
1 0
2 1
3 2
7

数据范围

1≤p≤n≤1051\le p\le n\le10^5,k∈{0,1}k\in\{0,1\}。ai,bia_i,b_i 为非负整数。原题范围段给出的上界为 ai<107a_i<10^7、bi<1012b_i<10^{12}。