Налийте якомога швидше
Обмеження: 2 сек., 256 МіБ
На барній стійці послідовно стоять n кубків. Спочатку вони всі пусті, але нам відомо, що в i-тий кубок необхідно налити рівно ai грам рідини. За одну секунду бармен може вибрати неперервний проміжок кубків і або налити в кожен з них по одному граму або налити в кожен з них по x грамів. Виливати рідину з кубка строго заборонено. Вас цікавить за який найменший проміжок часу бармен може виконати замовлення.
Вхідні дані
У першому рядку знаходяться два цілих числа: n та x. В наступному рядку дано n цілих чисел ai.
Вихідні дані
У єдиному рядку виведіть одне ціле число — мінімальну кількість секунд необхідну для наповнення усіх кубків.
Обмеження
1≤n≤300000,
1≤x,ai≤109.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
6 3 1 1 1 4 3 3 | 2 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 5 4 0 4 0 4 | 12 |
Джерело: The Algo Battles 2023 - Етап 2