Pour as fast as possible

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

There are \(n\) cups standing in a row on the bar counter. Initially they are all empty, but we know that exactly \(a_i\) grams of liquid must be poured into the \(i\)-th cup. In one second, the bartender can choose a contiguous subsegment of cups and either pour one gram into each of them or pour \(x\) grams into each of them. Pouring liquid out of a cup is strictly prohibited. You are interested in the minimum amount of time in which the bartender can fulfill the order.

Input

The first line contains two integers: \(n\) and \(x\). The next line gives \(n\) integers \(a_i\).

Output

In a single line, output a single integer — the minimum number of seconds required to fill all the cups.

Constraints

\(1 \le n \le 300000\),

\(1 \le x, a_i \le 10^9\).

Samples