5. Grandma's Jam
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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

Output a single integer — the minimum amount of jam discarded.

Scoring

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.

Examples
Input
3 10
5 8 6
Output
3
Input
1 2
2
Output
0
Input
1 10000001
1000000000
Output
9999901
Note

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.