3250 - 付费自习室

题目描述

A 暑假在家门口的付费自习室学习。

自习室的收费规则如下:

  1. 首次来自习室,需要缴纳 X 元的费用,成为自习室会员。

  2. 在成为会员之后的当天起,可以购买连续 D 天的自习位使用权,每天仅需 1 元。购买了使用权之后,也可以选择不来自习。

  3. 如果中途有 \ge 1 天没有购买自习位使用权,会员资格失效,下次再来,需要重新缴纳 X 元成为自习室会员 。

A 制定了暑假自习计划,暑假中的 N 天,他会来付费自习室学习。请帮助小 A 计算出,他最少需要花费多少钱?

输入

1 行读入 2 个整数 N,X

2 行读入 N 个整数,第 i 个数 D_i ,表示小 A 在未来第 D_i 天会来自习室学习。

输出

输出一个整数,表示小 A 最少需要花费多少钱。

样例

输入

2 4
7 9

输出

7

输入

3 3
1 10 12

输出

10

输入

8 6
1 3 10 14 20 30 35 50

输出

45
说明

样例 1 解释

A 暑假有 2 天来自习室。

第一次来自习室是暑假第 7 天,他缴纳 4 元购买会员,又缴纳了 3 元购买了第 7 8 9 三天的自习位使用权,第 8 天他们没有来自习,第 9 天他来自习。

可以发现,这是最优惠的方案。

样例 2 解释

A 暑假有 3 天来自习室。

第一次来自习室是暑假第 1 天,他缴纳 3 元购买会员,又缴纳了 1 元购买了第 1 天的自习位使用权。

第二次来自习室是暑假第 10 天,他缴纳 3 元购买会员,又缴纳了 3 元购买了第 10 11 12 天的自习位使用权。

因此,他最少需要花费 10 元。

数据范围

对于 30\% 的数据,满足 1 \le N \le 10

对于 100\% 的数据,满足 1 \le N \le 10^51 \le D_i \le 10^{14}1 \le X \le 10^9

测试数据保证所有的 D_i 按照单调递增的顺序给出。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 589
通过人数 194
金币数量 0 枚
难度 基础


上一题 下一题