Xeroxinator
Dr. Heinz Fufelschmertz is tired of standing in queues. So he created the xeroxinator, a device that creates human clones. And now he sends his clones to stand in queues instead of himself. Unfortunately, the device has experienced an unexpected failure. Now too many clones of Heinz are being created, and they all go to the post office.
Today the post office is open for n minutes, numbered from 1 to n. At the beginning of the i-th minute, a[i] Doofenshmertz clones will come to the mail, and they will stand at the end of the queue. No more than b clones can be served at the post office in one minute - if there are at least b clones in the queue, then b of the first of them are served, otherwise everyone who is in the queue is served. All clones served at the i-th minute will leave the mail at the end of the i-th minute. At the end of the n-th minute, the mail will close. All the clones that they did not have time to serve will stand for another minute indignant, and disperse. Help Heinz calculate the total time spent by all the clones at the post office.
Note that if the clone entered the mailbox at the beginning of the ith minute and left at the end of the ith minute, then it spent one minute in the mailbox.
Input
The first line contains two integers n and b (1 ≤ n ≤ 10^5, 1 ≤ b ≤ 10^8) - the number of minutes that the mail works, and the number of clones that can be served per minute.
The second line contains n integers a[i] (0 ≤ a[i] ≤ 10^8) - the number of clones that will be sent to the mail at the start of i-th minute.
Output
Print a single integer - the total time that all clones will spend in the mail.