At the start of the semester, your teacher hands you a course outline. The outline states that there will be $N$ tests, each of which will be out of $M$ marks.

Your school has a weird scoring system. Instead of using percentages or letter grades, your school simply provides the average of your test scores on your report card.

You would like your parents to see a mark that is higher than or equal to $K$ on your report card.

As of right now, you have predicted that for each test $i$ $(1\le i\le N)$ that will happen, you will score $x_i$ if you do not study at all. From there, you can increase your mark by $1$ point for every $y_i$ hours you study.

Find out the minimum total number of hours you need to study for all tests. Note that each test is weighted the same.

Input Specification

Line $1$ contains integers $N$, $M$, and $K$, separated by a space. $N$ is the number of tests throughout the semester. $M$ is the number of marks that each test is scored out of. $K$ is the minimum mark that you will accept on your report card.

Lines $2$ to $N+1$: The $(i+1{)}^{th}$ line contains the integers $x_i$ and $y_i$, separated by a space, where $1\le i\le N$. $x_i$ is the predicted score on test $i$ if you do not study at all. $y_i$ is the number of hours you need to study to increase your score by $1$ on that test.

Output Specification

Output the minimum number of hours you need to study to get a mark of at least $K$ on your report card.

Constraints

• $1\le N\le {10}^5$
• $1\le M\le {10}^6$
• $0\le K,x_i\le M$
• $0\le y_i\le {10}^6$

Subtasks

Subtask 1 [10%]

• $1\le N,M\le 100$
• $0\le y_i\le 100$

Subtask 2 [30%]

• $1\le N\le 5000$
• $1\le M\le 500$

Subtask 3 [60%]

No additional constraints.

Sample Input

5 7 6
5 3
6 4
7 1
1 5
3 3

Sample Output

27

Sample Explanation

You can increase your score on the first test up to 7 by studying for 6 hours. You can then increase your score on the second test by 1 point with 4 hours of studying. You can increase your score on the fourth test by 1 point with 5 hours of studying. Finally, increase your score on the last test up to 7 by studying for 12 hours.

Note that you cannot increase your score on any test to have a value of greater than 7 as the tests are out of 7 marks.