Grandmother stores jam in a long container divided into $$$N$$$ consecutive sections. Section $$$i$$$ contains $$$a_i$$$ units of jam.
Grandmother chooses a non-empty contiguous range of sections—from section $$$i$$$ to section $$$j$$$ inclusive — and collects all the jam from these sections into jars (she does this exactly once). The boundaries of this range can be the partitions between sections or the ends of the container.
Each jar has a capacity of $$$M$$$. Grandmother fills only complete jars; any remaining jam that is insufficient to fill another full jar is discarded.
Find the minimum amount of jam that must be discarded.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 2\,000\,000$$$, $$$N \lt M \le 10\,000\,001$$$).
The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).
Output a single integer — the minimum amount of jam discarded.
Subtask 1 (up to 30 points): $$$N \le 2\,000$$$.
Subtask 2 (up to 30 points): $$$N \le 200\,000$$$.
Subtask 3 (up to 40 points): no additional constraints.
3 105 8 6
3
1 22
0
1 100000011000000000
9999901
Additional test cases, which were not present during the competition, have been added to the problem.
Note for Python users. A sequence of integers separated by spaces can be read as follows:
a = [int(x) for x in input().split()]
Note on fast I/O. The final subtask involves a large volume of input data. In some programming languages, you may need to use specific techniques to speed up input operations.
In C++, simply add the following lines to the beginning of your main function:
ios_base::sync_with_stdio(false);
cin.tie(0);
In Java, use BufferedInputStream and read integers directly from the byte stream. Using Scanner for large inputs can be too slow.
In C#, use BufferedStream wrapped around Console.OpenStandardInput() and read integers from the byte stream. Reading an entire line using Console.ReadLine().Split() creates many string objects, which can be both time-consuming and memory-intensive.
Python users are advised to submit their solutions using PyPy.