题目描述

Bessie likes to watch shows on Mooloo. Because Bessie is a busy cow, she has planned a schedule for the next $N (1 \le N \le 10^5)$ days that she will watch Mooloo. Because Mooloo is a paid subscription service, she now needs to decide how to minimize the amount of money she needs to pay.

Mooloo has an interesting subscription system: it costs $d+K(1 \le K \le 10^9)$ moonies to subscribe to Mooloo for d consecutive days. You can start a subscription at any time, and you can start a new subscription as many times as you desire if your current subscription expires. Given this, figure out the minimum amount of moonies Bessie needs to pay to fulfill her schedule.

输入格式

The first line contains integers $N$ and $K$.

The second line contains $N$ integers describing the days Bessie will watch Mooloo: $1 \le d_1<d_2< \cdots <d_N \le 10^{14}$.

输出格式

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

题目大意

题目描述

贝茜喜欢看 Mooloo 的演出。因为她是一只忙碌的奶牛，她计划在接下来的 $N (1 \le N \le 10^5)$ 天去看演出。因为 Mooloo 提供了订阅服务，她想要使她花费的钱最少。

Mooloo 有一个有趣的订阅服务系统：若要在此之后的连续 $d$ 天看演出，则在订阅时需要花费 $d+K(1 \le K \le 10^9)$ 个单位价格。你可以随时订阅；若本次订阅已经过期，你可以根据需要订阅多次。基于以上条件，请计算出贝茜最少要花费多少个单位价格，才能完成她的计划。

输入格式

第一行输入两个正整数 $N$ 和 $K$。

第二行输入 $N$ 个正整数，表示在这些天里，贝茜会看 Mooloo 的演出：$1 \le d_1<d_2<\cdots<d_N \le 10^{14}$。

输出格式

请注意，此问题中可能需要使用 64 位整数数据类型（如 C 或 C++ 中的 long long）。

样例 #1 解释

贝茜在第 $7$ 天时，购买了 $3$ 天的订阅，共花费 $d+K=3+4=7$ 个单位价格。

样例 #2 解释

贝茜在第 $1$ 天时，购买了 $1$ 天的订阅，花费 $d+K=1+3=4$ 个单位价格；在第 $10$ 天时，也购买了 $1$ 天的订阅，花费 $d+K=1+3=4$ 个单位价格。贝茜一共花费了 $8$ 个单位价格。

translated by liyuanchen2021

2 4
7 9

7

2 3
1 10

8

提示

Explanation for Sample 1

Bessie buys a three-day subscription on day $7$, spending $d+K=3+4=7$ moonies.

Explanation for Sample 2

Bessie first buys a one-day subscription on day $1$, spending $d+K=1+3=4$ moonies. Bessie also buys a one-day subscription on day $10$, spending $d+K=1+3=4$ moonies. In total, Bessie spends $8$ moonies.

SCORING

• Inputs $3-5$: $N \le 10$
• Inputs $6-12$: No additional constraints.