Ваня хочет сдать n экзаменов и получить стипендию. Для получения стипендии средний балл за все экзамены должен быть не меньше avg. Максимальная оценка за экзамен не может превышать r. Ваня сдал экзамены, и за i-й экзамен получил оценку ai. Чтобы поднять за i-й экзамен оценку на 1 балл, Ваня должен сдать bi рефератов. Повышать оценку за экзамен можно несколько раз.
Какое минимальное количество рефератов должен сдать Ваня, чтобы получить стипендию?
Выходные данные
В первую строку выведите минимальное количество рефератов.
Примечание
В первом примере Ваня может сдать 2 реферата по 3 экзамену, подняв свою оценку на 2 балла, и 2 реферата по 4 экзамену, подняв свою оценку на 1 балл.
Во втором примере Ване не нужно сдавать рефераты, так как его балл и так выше среднего.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5 4
5 2
4 7
3 1
3 2
2 5
|
4
|
|
2
|
2 5 4
5 2
5 2
|
0
|