只要努力飞翔，即使再弱小的蝴蝶也可以飞的很高
4360 - achievement
有n个成就，每个成就都有难度，对于第i个成就，它的难度一开始为ai，之后每秒会增加bi。你每 秒钟都可以完成任意一个还未完成的成就，求完成k个成就的总难度最小是多少。 另外，本题还有一个参数mode。如果mode=true，则你可以在一开始将某个成就的难度降为0（但 每秒钟依然会增加），之后你随时可以完成该成就。
Input
第一行三个整数n,k,mode。 接下来n行，每行两个整数a,b(0≤a,b≤106)，描述一个成就。
Output
一行一个整数，描述答案。
Examples
Input
3 3 0 0 1 1 2 2 3
Output
7
Hint
1<=N<=10^5