241977 - 快递驿站

题目描述

小镇上的快递驿站只有一名工作人员。今天依次有 n 个包裹需要寄出,第 i 个包裹在时刻 a_i 到达驿站,且到达时刻严格递增,即先到的包裹编号更小。由于驿站的打包机只有一种规格,每个包裹都需要连续花费 k 分钟来处理,一旦开始就不能中断。

若某个包裹到达时上一件还没有处理完,它就在一旁排队等待;若上一件处理完时它还没有到,工作人员就空闲等待它到达。

请计算处理完全部 n 个包裹的时刻。

输入

第一行,两个整数 n、k,分别表示包裹数量和每个包裹的处理时长。

第二行,n 个整数 a_1, a_2, ..., a_n,其中 a_i 表示第 i 个包裹到达驿站的时刻。数据可能分布在多行中。

输出

输出一个整数,表示处理完全部 n 个包裹的时刻。

样例

输入

3 3
1 5 10

输出

13
说明
  • 测试点 1~3(30 分):n ≤ 100,1 ≤ a_i, k ≤ 10^4。

  • 测试点 4~10(70 分):n ≤ 10^5,1 ≤ a_i, k ≤ 10^9。

包裹按到达时刻严格递增的顺序给出,即 a_1 < a_2 < ... < a_n。

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 22
通过人数 8
金币数量 2 枚
难度 入门


上一题 下一题