Задача Dogging. Василько Пупкін нещодавно придбав собі песика. На зоологічних форумах він вичитав, що песикам цієї породи необхідно щонайменше K прогулянок за будь-яких два послідовних дні, щоб бути щасливими. До прикладу, якщо K = 7 та Василь погуляв з песиком тричі вчора, то сьогодні йому треба вигуляти його щонайменше чотири рази. Вася вже відмітив бажану кількість прогулянок (з урахуванням своїх справ) на наступні N днiв, але боїться, що іноді прогулянок буде замало. Тож він просить Вас допомогти йому визначити, яку кількість прогулянок треба зробити додатково, щоб його вірний пес був щасливий.
Технiчнi умови. Програма Dogging читає два натуральних числа N i K (N,K ≤ 105) - кількість днів i кількість необхідних прогулянок. Далі програма читає ще N цілих невід’ємних чисел - кількість запланованих прогулянок на кожний з наступних N днів. Кожне з чисел не перевищує 105. Програма повинна виводити єдине число - мінімальну кількість додаткових прогулянок, які необхідно зробити.
Приклади
|
Введення |
Виведення |
|
4 5 2 2 1 3 |
2 |
|
4 1 0 0 0 0 |
2 |