← 返回题目列表

Codeforces · 492/C

C. 万尼亚和考试

中文机器翻译题面 查看原题

Vanya 希望通过 n 次考试并获得学术奖学金。如果所有考试的平均成绩至少达到avg,他将获得奖学金。考试成绩不能超过r。 Vanya 已通过考试并获得第 i 次考试的 ai 级。为了将第 i 次考试的成绩提高 1 分,Vanya 必须写 bi 论文。他可以多次提升考试成绩。

Vanya 需要写多少论文才能获得奖学金?

输入

第一行包含三个整数 n、r、avg (1 ≤ n ≤ 105, 1 ≤ r ≤ 109, 1 ≤ avg ≤ min(r, 106)) - 分别是考试次数、最高成绩和要求的平均绩点。

以下 n 行中的每一行都包含空格分隔的整数 ai 和 bi (1 ≤ ai ≤ r, 1 ≤ bi ≤ 106)。

输出

在第一行打印最少的论文数量。

示例

输入 #1

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

输出 #1

4

输入 #2

2 5 4
5 2
5 2

输出 #2

0

注意

在第一个样本中,Vanya 可以为第 3 次考试写 2 篇论文,将其成绩提高 2 分,为第 4 次考试写 2 篇论文,将其成绩提高 1 分。

在第二个样本中,Vanya 不需要写任何论文,因为他的平均分已经高于平均水平。