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?

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}).

提交代码