Background

  "A light rain makes all flowers fresh; with one thunder, Jingzhe begins."

---

  At noon, in the lounge, on Ayang's shoulder.

  "I have a wish: to take part in the National Music Festival, win an award, and together with Ayang, break free from this bitter sea of training."

  "Coming for love, working hard to get away... is that so?"

  The midday sunlight seeps through the curtains and gently touches the sleepy person's cheeks. Tianyi's left hand quietly rests on the guitar in Ayang's arms,

  "Zheng—"

  The hibernating insects are awakened by the thunder, and no one promises them that the rain will come.

---

  Jingzhe "I am willing to grind the years into a looking glass and search all across this starry sky, focusing the faint light into my palm and holding it tight without letting go."

Problem Description

The contest is getting close, and various tests have become more frequent. As the professional analyst for Tianyi and the others, your job is to do statistics and analysis of the team members' performance. In short, a certain leader is coming to visit, so you are required to revise a pleasing-looking analysis report.

In the existing $n$ tests, for a particular player, their fluctuation value in the $i$-th test is a non-negative integer $a_i$. A smaller fluctuation value means the player's mentality and performance are more stable, so you need to "slightly adjust" the fluctuation sequence $\{a_n\}$ into another non-negative integer sequence $\{b_n\}$. However, you cannot be too dishonest, yet the report must look good, so $\{b_n\}$ must satisfy:

• $\{b_n\}$ is monotone non-increasing, because the player is getting better and better;
• For each $i$, if $b_i<a_i$, the teacher will be unhappy, so you need to spend $C$ units of energy to persuade the teacher (where $C$ is a given constant);
• For each $i$, if $a_i\le b_i$, the player will be unhappy, possibly very unhappy, so you need to spend $b_i-a_i$ units of energy to comfort the player.

You want, under these conditions, to minimize the total energy spent. As an experienced competitive programming contestant, you should compute this minimum value yourself.

Formal statement

Given a non-negative integer sequence $\{a_n\}$, define the function $f(x,y)$ as

$$f(x,y)=\begin{cases} x-y,&x\ge y\\ C,&x< y \end{cases},$$

where $C$ is a given constant. Construct a non-increasing non-negative integer sequence $\{b_n\}$ to minimize

$$\sum_{i=1}^nf(b_i,a_i).$$

You only need to output this minimum value.

Input Format

The first line contains two integers, the sequence length $n$ and the given constant $C$.

The next line contains the sequence $\{a_n\}$.

Output Format

Output one line with one integer, the minimum value.

3 3
4 5 2

1

10 5
12 17 20 2 0 1 13 6 10 1

26

Hint

Sample #1 Explanation

Construct $\{b_n\}=\{5,5,2\}$. Then:

$$\begin{aligned} \sum_{i=1}^nf(b_i,a_i) &= f(5,4)+f(5,5)+f(2,2)\\ &= 1+0+0\\ &= 1. \end{aligned}$$

Sample #2 Explanation

Construct $\{b_n\}=\{12,11,4,2,1,1,1,1,1,1\}$, and you can obtain the answer.

Constraints

This problem uses Subtask scoring.

Let $V$ be the value range of the elements in $\{a_n\}$ and the constant $C$.

For $100\%$ of the data, $1\le n\le10^6$, $V\subseteq[0,10^9]$.

For different subtasks, the constraints are as follows:

Subtask ID	$n$	$V$	Special Property	Score
$1$	$\le10^3$	$\subseteq[0,10^9]$	None	$25$
$2$	$\le10^5$	$\subseteq[0,10^2]$		$15$
$3$	$\le10^6$	$\subseteq[0,10^9]$	A	$5$
$4$			B	$15$
$5$	$\le10^5$		None	$20$
$6$	$\le10^6$

• Special Property A: For the constant $C$, $C = 0$.
• Special Property B: For the sequence $\{a_n\}$, the elements are monotone increasing.

Translated by ChatGPT 5