24502번 - blobsad

문제

연구소에 동거하는 채완이와 주환이는 블롭을 아주 좋아한다. 그래서 둘은 연구소에서 블롭을 키운다.

둘은 1ドル \times 1$ 크기의 정사각형 $N$개로 나누어진 1ドル \times N$ 크기의 직사각형 통 안에 블롭을 키우고 있으며, $i$번째 1ドル \times 1$ 정사각형에는 블롭 $A_i$마리를 키운다.

그런데 어느 날, 채완이와 주환이는 블롭들이 슬퍼한다는 사실을 알아차렸다.

연구 끝에 블롭은 같은 칸에 있는 블롭의 수가 $K$의 배수가 아니면 슬퍼한다는 사실을 알 수 있었고, 통에 있는 블롭을 적절히 옮겨 슬퍼하지 않게 만들려고 한다.

그러나 1ドル$초마다 하나의 블롭만 옮길 수 있으며, 블롭은 여러 칸을 한번에 움직이는 것을 싫어하기 때문에 인접한 칸으로만 옮길 수 있다. 채완이와 주환이는 할 일이 많이 있기에 최대한 빠르게 블롭을 옮기는 일을 해결하려고 한다.

채완이와 주환이를 위해 블롭을 옮기는 일을 마칠 수 있는 최소 시간을 구해주자.

입력

첫째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다.

둘째 줄에 1ドル \times 1$ 정사각형에 들어가 있는 블롭의 수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

출력

채완이와 주환이가 이 일을 마칠 수 있는 최소 시간을 초 단위로 출력한다. 만약, 마칠 수 없다면 blobsad를 출력한다.

제한

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

힌트