5. Бабушкино варенье
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бабушка хранит варенье в длинной ёмкости, разделённой на $$$N$$$ последовательных секций. В секции с номером $$$i$$$ находится $$$a_i$$$ единиц варенья.

Бабушка выбирает непустой участок из подряд идущих секций — с $$$i$$$-й по $$$j$$$-ю включительно — и сливает из него всё варенье в банки (она выполняет это один раз). Границами участка могут служить перегородки между секциями или края ёмкости.

Объём одной банки равен $$$M$$$. Бабушка заполняет только целые банки, а варенье, которого не хватило на следующую полную банку, выбрасывает.

Найдите минимальное количество варенья, которое придётся выбросить.

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

В первой строке записаны два целых числа $$$N$$$ и $$$M$$$ ($$$1 \le N \le 2\,000\,000$$$, $$$N \lt M \le 10\,000\,001$$$).

Во второй строке записаны $$$N$$$ целых чисел $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).

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

Выведите одно целое число — минимальное количество выброшенного варенья.

Система оценки

Подзадача 1 (до 30 баллов): $$$N \le 2\,000$$$.

Подзадача 2 (до 30 баллов): $$$N \le 200\,000$$$.

Подзадача 3 (до 40 баллов): без дополнительных ограничений.

Примеры
Входные данные
3 10
5 8 6
Выходные данные
3
Входные данные
1 2
2
Выходные данные
0
Входные данные
1 10000001
1000000000
Выходные данные
9999901
Примечание

В задачу были добавлены дополнительные тесты, которых не было во время олимпиады.

Примечание для пишущих на Python. Набор целых чисел, записанных через пробел, можно прочитать так:

a = [int(x) for x in input().split()]

Примечание по быстрому вводу. В последней подзадаче нужно вводить большой объём данных. В некоторых языках для этого нужно использовать специальные способы ускорения ввода.

В языке C++ достаточно добавить в начало функции main следующие строки:

ios_base::sync_with_stdio(false); 
cin.tie(0);

В Java используйте 'BufferedInputStream' и считывайте целые числа из байтов. 'Scanner' на большом входе может работать слишком медленно.

В C# используйте 'BufferedStream' поверх 'Console.OpenStandardInput()' и считывайте целые числа из байтов. Чтение всей строки через 'Console.ReadLine().Split()' создаёт много строк и может потребовать слишком много времени и памяти.

Пишущим на языке Python рекомендуется сдавать эту задачу на PyPy.