题目描述

小 x 励志当一名医生。某年某月某日，在 A 市爆发了一场疫情。病毒繁衍地非常快，每个病 人病情的严重程度可以用一个非负整数来衡量。这个城市有 $n$ 个病人。在小 x 刚到达这个城市的时候，每个病人的病情可以用 $b$ 表示。每过一个时刻，病人的病情会增加 $a$。

注意上面所述的 $a,b$ 对每一个病人不一定相同。救治一个病情严重程度为 $x$ 的病人，小 x 需要消耗 $x$ 点体力。小x刚到达这个城市的时候就可以开始救治。

有些时候，小 x 会带来一瓶超级药水，在他到达这个城市的时候可以给某个病人服下（不消耗时间，也不一定要最先救治这个病人），那么这个病人的 $b$ 值会变成 $0$。

只要成功救治了 $p$ 个病人，就可以认为病情稳定，小 x 就可以休息了。问小 x 最少需要消耗多少体力。

输入格式

第一行有三个整数 $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

数据规模与约定

对于 $100\%$ 的数据，$l \le n \le 10^5$，$l \le P \le n$，$0\le k\le l$，$0<a<10^7$，$0<B<10^{12}$。

题目来源

By xyz111