题目描述

Vanya 想要通过 $n$ 门考试并获得奖学金。如果所有考试的平均分不少于 $avg$，他就能获得奖学金。每门考试的分数不能超过 $r$。Vanya 已经通过了所有考试，第 $i$ 门考试的分数是 $a_{i}$。要将第 $i$ 门考试的分数提高 1 分，Vanya 需要写 $b_{i}$ 篇作文。他可以多次提高考试成绩。

求 Vanya 至少需要写多少篇作文才能获得奖学金？

输入格式

第一行包含三个整数 $n$，$r$，$avg$（$1 \leq n \leq 10^5$，$1 \leq r \leq 10^9$，$1 \leq avg \leq \min(r, 10^6)$），表示考试门数、单门最高分和所需的平均分。

接下来的 $n$ 行，每行包含两个用空格分隔的整数 $a_i$，$b_i$（$1 \leq a_i \leq r$，$1 \leq b_i \leq 10^6$）。

输出格式

输出一个整数，表示获得奖学金至少需要写多少篇作文。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

2 5 4
5 2
5 2

输出 #2

0

说明/提示

在第一个样例中，Vanya 可以为第 3 门考试写 2 篇作文提高 2 分，为第 4 门考试写 2 篇作文提高 1 分。

在第二个样例中，Vanya 已经达到了要求的平均分，无需再写作文。