blobsad

Time limit1sMemory limit1024 MB

Summary

Move blobs between adjacent cells so every cell holds a multiple of K, minimizing total moves, or report impossibility.

Level: Medium7 of 10
Topics: Greedy, Prefix sum, Math, Array
Solved: No attempts yet

Problem

Chaewan and Juhwan, who live together in a laboratory, love blobs. So the two of them raise blobs in the laboratory.

They raise blobs in a rectangular tank of size $1 \times N$ divided into $N$ squares of size $1 \times 1$ , and in the $i$ -th $1 \times 1$ square they raise $A_i$ blobs.

One day, Chaewan and Juhwan noticed that the blobs are sad.

After research, they found out that a blob is sad if the number of blobs in its square is not a multiple of $K$ , and they want to move the blobs in the tank appropriately so that no blob is sad.

However, only one blob can be moved per second, and since blobs dislike moving several squares at once, a blob can only be moved to an adjacent square. Chaewan and Juhwan have a lot of work to do, so they want to finish moving the blobs as quickly as possible.

For Chaewan and Juhwan, find the minimum time in which the task of moving the blobs can be finished.

Input

The first line gives $N$ and $K$ , separated by a space.

The second line gives the numbers of blobs in the $1 \times 1$ squares, $A_1, A_2, \cdots, A_N$ , separated by spaces.

Output

Print the minimum time in seconds in which Chaewan and Juhwan can finish this task. If they cannot finish it, print blobsad.

Constraints

$1 \le N \le 10^6$
$1 \le K \le 10^9$
$1 \le A_i \le 10^9$ $(1 \le i \le N)$

Examples2

Example 1
Input
```
5 5
1 1 1 1 1
```
Expected output
```
6
```
Example 2
Input
```
5 4
1 1 1 1 1
```
Expected output
```
blobsad
```