wjruwhtu

13.01.2020 08:03

Информатика

Есть ответ 👍

В Берляндском государственном университете есть студенческий буфет. Рассмотрим его работу в один из учебных дней. Во всем университете n перемен, перед каждой из которых в буфет привозят ровно k булочек с маком (считаем, что в начале дня буфет пустой). Каждая булочка может храниться в буфете h перемен. В течение i-й перемены (1≤i≤n) в буфет приходят ровно ai студентов. Студенты приходят в буфет голодными, поэтому цель каждого из них — купить ровно одну булочку и стать сытым. Каждый студент может стоять в очереди за булочкой ровно один раз в день во время одной перемены. Сотрудник буфета работает с молниеносной скоростью, поэтому время продажи каждой булочки ничтожно мало и в условиях задачи роли не играет. Однако, если студенту не хватает булочки, он расстраивается и уходит голодным.

Определите минимальное количество студентов, которые останутся голодными.

Входные данные

Первая строка содержит три целых числа n, k, h (1≤n≤k≤105, 1≤h≤100) — количество перемен, количество булочек, привозимых в буфет перед каждой переменой, и срок хранения каждой булочки.

Вторая строка содержит n целых чисел ai (1≤ai≤105) — количество студентов, пришедших в буфет на i-й перемене.

Выходные данные

Выведите единственное целое число — минимальное количество студентов, которые останутся голодными.
входные данные
5 3 2
2 4 3 6 8
выходные данные
8