小 A 暑假在家门口的付费自习室学习。
自习室的收费规则如下:
首次来自习室,需要缴纳 X 元的费用,成为自习室会员。
在成为会员之后的当天起,可以购买连续 D 天的自习位使用权,每天仅需 1 元。购买了使用权之后,也可以选择不来自习。
如果中途有 \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
小 A 暑假有 2 天来自习室。
第一次来自习室是暑假第 7 天,他缴纳 4 元购买会员,又缴纳了 3 元购买了第 7 8 9 三天的自习位使用权,第 8 天他们没有来自习,第 9 天他来自习。
可以发现,这是最优惠的方案。
小 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^5,1 \le D_i \le 10^{14},1 \le X \le 10^9。
测试数据保证所有的 D_i 按照单调递增的顺序给出。