Ваня хочет сдать n экзаменов и получить стипендию. Для получения стипендии средний балл за все экзамены должен быть не меньше avg. Максимальная оценка за экзамен не может превышать r. Ваня сдал экзамены, и за i-й экзамен получил оценку ai. Чтобы поднять за i-й экзамен оценку на 1 балл, Ваня должен сдать bi рефератов. Повышать оценку за экзамен можно несколько раз.
Какое минимальное количество рефератов должен сдать Ваня, чтобы получить стипендию?
В первой строке записано три целых числа n, r, avg (1 ≤ n ≤ 105, 1 ≤ r ≤ 109, 1 ≤ avg ≤ min(r, 106)) — количество экзаменов, максимальный балл и требуемый средний балл соответственно.
В каждой из последующих n строк через пробел записаны целые числа ai и bi (1 ≤ ai ≤ r, 1 ≤ bi ≤ 106).
В первую строку выведите минимальное количество рефератов.
В первом примере Ваня может сдать 2 реферата по 3 экзамену, подняв свою оценку на 2 балла, и 2 реферата по 4 экзамену, подняв свою оценку на 1 балл.
Во втором примере Ване не нужно сдавать рефераты, так как его балл и так выше среднего.
5 5 4 5 2 4 7 3 1 3 2 2 5
4
2 5 4 5 2 5 2
0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач