绝世好题

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

QQ 去爬山啦!

Description

QQ 有两种方式爬山:

1. 从一个山峰爬到相邻山峰,花费 max(0,hihj)\max(0, h_i - h_j)

2.瞬移 移到任意一个山峰,花费 PP

QQ 想知道他从 11 号山峰开始经过 nn 个山峰所需要的最小体力。

Format

Input

第一行两个整数 n,Pn, P。 然后 nn 个数字,代表山峰的高度 hih_i

Output

一行,代表答案

Samples

6 5
100 1 3 0 10 100
7

Limitation

2n5×1052 \le n \le 5 \times 10^5

0P10100 \le P \le 10^{10}

0hi10200 \le h_i \le 10^{20}

保证答案不超 long long

菜就多练

Not Attended
Status
Done
Rule
IOI(Strict)
Problem
19
Start at
2024-3-2 19:15
End at
2024-4-13 11:15
Duration
1000 hour(s)
Host
Partic.
3