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 不需要写任何论文,因为他的平均分已经高于平均水平。