Vanya wants to pass $*n*$ exams and get the academic scholarship. He will get the scholarship if the average grade mark for all the exams is at least $*avg*$. The exam grade cannot exceed $*r*$. Vanya has passed the exams and got grade $*a*_{*i*}$ for the $*i*$-th exam. To increase the grade for the $*i*$-th exam by 1 point, Vanya must write $*b*_{*i*}$ essays. He can raise the exam grade multiple times.

What is the minimum number of essays that Vanya needs to write to get scholarship?

Input

The first line contains three integers $*n*$, $*r*$, $*avg*$ ($1 ≤ *n* ≤ 10^{5}$, $1 ≤ *r* ≤ 10^{9}$, $1 ≤ *avg* ≤ *min*(*r*, 10^{6})$) — the number of exams, the maximum grade and the required grade point average, respectively.

Each of the following $*n*$ lines contains space-separated integers $*a*_{*i*}$ and $*b*_{*i*}$ ($1 ≤ *a*_{*i*} ≤ *r*$, $1 ≤ *b*_{*i*} ≤ 10^{6}$).

Output

In the first line print the minimum number of essays.

Note

In the first sample Vanya can write 2 essays for the 3rd exam to raise his grade by 2 points and 2 essays for the 4th exam to raise his grade by 1 point.

In the second sample, Vanya doesn't need to write any essays as his general point average already is above average.