#2174. Vanya and Exams
-
ID: 2174
传统题
1000ms
256MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
Vanya and Exams
Description
Vanya想通过n次考试来获得奖学金。如果所有考试的平均分数不低于avg，他就能获得奖学金。考试成绩较差时，Vanya也可以通过写论文来提高分数，但提高后的成绩不能超过r（加完得到的分数不能超过 r）。ai是Vanya第i次考试已经获得的分数，为了将第i次考试的成绩提高1分，Vanya必须写bi篇论文。通过写论文他可以多次提高考试成绩。
为了获得奖学金，Vanya最少需要写多少篇论文？
输入
第一行包含三个整数n，r，avg（1≤n≤10^5，1≤r≤10^9，1≤avg≤min(r,10^6)）--分别是考试次数，最高成绩和要求的平均分。
下面的n行中的每一行都包含空间分隔的整数ai和bi（1≤ai≤r，1≤bi≤10^6）。
输出
在第一行打印最小的论文数量。
Examples
Input
5 5 4 5 2 4 7 3 1 3 2 2 5
Output
4
Input
2 5 4 5 2 5 2
Output
0
Note
在第一个样例中，Vanya可以在第三次考试中写2篇论文，使他的成绩提高2分，在第四次考试中写2篇论文，使他的成绩提高1分。在第二个例子中，Vanya不需要写任何论文，因为他的总平均分已经超过了平均水平。