题目描述

有 $n$ 个成就，对于第 $i$ 个成就，它的初始难度为 $a_i$，之后每秒难度会增加 $b_i$。

你每秒钟都可以完成任意一个还未完成的成就，求完成 $k$ 个成就的总难度最小是多少。

另外，本题还有一个参数 $mode$。如果 $mode$ 为 $\texttt{true}$，则你可以在一开始将某个成就的难度降为 $0$。

输入格式

第一行三个整数 $n,k,mode$，分别表示成就数量，完成成就数量，和参数。

接下来 $n$ 行，每行两个整数 $a_i,b_i$，分别表示一个成就的初始难度，和每秒增加的难度。

输出格式

一行一个整数，描述答案。

3 3 0
0 1
1 2
2 3

7

提示

对于 $100\%$ 的数据，$1\le n\le 10^5$，$0\le a_i,b_i\le 10^6$。

题目来源

$\texttt{Lydsy3953 Control}$