제록시네이터

닥터 하인츠 푸펠슈메르츠는 줄 서는 일에 지쳤다. 그래서 사람의 클론을 만드는 장치인 제록시네이터를 만들었다. 이제 그는 자기 대신 클론을 보내 줄을 세운다. 그런데 장치에 예상치 못한 고장이 났다. 이제 하인츠의 클론이 너무 많이 만들어지고, 그 클론들이 모두 우체국으로 간다.

오늘 우체국은 1분부터 $n$분까지 $n$분 동안 운영한다. $i$분 시작 시점에 $a_i$명의 푸펠슈메르츠 클론이 우체국에 들어와 대기열 맨 뒤에 선다. 1분 동안 우체국은 최대 $b$명의 클론을 처리한다. 대기열에 $b$명 이상이 있으면 앞의 $b$명을 처리하고, 그렇지 않으면 대기열에 있는 모든 클론을 처리한다. $i$분에 처리된 클론은 $i$분이 끝날 때 우체국을 나간다. $n$분이 끝나면 우체국 문이 닫힌다. 처리되지 못한 클론은 1분을 더 서서 항의한 뒤 흩어진다. 하인츠를 위해 모든 클론이 우체국에 머문 시간의 총합을 구하라.

$i$분 시작 시점에 들어와 $i$분이 끝날 때 나간 클론은 우체국에 1분 머문 것이다.

첫 줄에 우체국이 운영하는 분 수 $n$과 1분에 처리할 수 있는 클론의 최대 수 $b$가 주어진다 ($1 \le n \le 100000$, $1 \le b \le 10^8$).

둘째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다. $a_i$는 $i$분 시작 시점에 도착하는 클론의 수이다 ($0 \le a_i \le 10^8$).

모든 클론이 우체국에서 보낸 시간의 총합을 정수 하나로 출력한다.