问题 F: 感应门

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:72 解决:45

题目描述

感应门会在有人经过的时候自动打开,冷却 d 秒后自动关闭。如果有人在感应门打开的状态下通过,那么冷却时间会重置,重新冷却 d 秒后再关闭。

在一段时间内,有 n 个人陆续通过了感应门,他们通过感应门的时间点分别是 �1,�2,⋯,��t1,t2,,tn,请计算感应门一共开放了多少时间。

输入

第一行:两个整数 n 与 dn 表示通过感应门的人数,d 表示感应门的冷却时间。
第二行:n 个整数 �1,�2,⋯,��t1,t2,,tn,每个数字表达一个人通过感应门的时间点。
  • 对于 50%50% 的数据,1≤�≤10001n1000
  • 对于 100%100% 的数据,1≤�≤100,0001n100,000
  • 1≤�1≤�2≤�3≤⋯≤��≤1,000,000,0001t1t2t3tn1,000,000,000
  • 1≤�≤1,000,000,0001d1,000,000,000


输出

单个整数,表示感应门总共开启了多少时间。

样例输入 复制

7 3
1 2 7 10 15 17 22

样例输出 复制

18