#O. 绝世好题

Type: Default

1000~6000ms

128MiB

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

小 $Q$ 去爬山啦！

Description

小 $Q$ 有两种方式爬山：

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

2.瞬移 移到任意一个山峰，花费 $P$

小 $Q$ 想知道他从 $1$ 号山峰开始经过 $n$ 个山峰所需要的最小体力。

Format

Input

第一行两个整数 $n, P$ 。然后 $n$ 个数字，代表山峰的高度 $h_i$ 。

Output

一行，代表答案

Samples

6 5
100 1 3 0 10 100

Limitation

$2 \le n \le 5 \times 10^5$

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

$0 \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

#O. 绝世好题

绝世好题

Background

Description

Format

Input

Output

Samples

Limitation

菜就多练

Status

Development

Support

#O. 绝世好题

绝世好题

Background

Description

Format

Input

Output

Samples

Limitation

菜就多练

Status

Development

Support

Don't have an account?

SIGN IN