问题1006--考试加成

1006: 考试加成

时间限制: 1 Sec  内存限制: 128 MB
提交: 351  解决: 106
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY为了拿奖学金,对于即将面临的n门考试平均分至少要达到 avg 分, 每门课的满分为 rBSNY凭自己的实力考试,第i门科目只能考ai分,但BSNY得到了魔法师的祝福,可以花费一些祝福值提高某科目的成绩,但最高不能超过满分。对于第i门科目,BSNY可以花费bi祝福值提高成绩1分。为了使得平均分达到avg分,问BSNY最少需要花费多少祝福值?

输入

第一行输入n, r, avg

接下来n行每行输入ai, bi (输入都为整数)

如果平均分已经大于等于avg分,输出0

输出

输出最少花费的祝福值

样例输入 Copy

5 5 4
5 2
4 7
3 1
3 2
2 5

样例输出 Copy

4

提示

增加第三门成绩2分,第四门成绩1分,需要花费4祝福值

【数据规模和约定】

1<=n<=10^5

1<=r<=10^9

1<= avg <= min(r, 10^6)

1<= ai <=r

1<= bi <=10^6

来源/分类

cf492C