168 人解决，200 人已尝试。
177 份提交通过，共有 449 份提交。
2.6 EMB 奖励。
5112. 青蛙游戏
单点时限: 1.0 sec
内存限制: 128 MB
一条马路上趴着很多青蛙，佩奇正好非常无聊，打算逗弄一下这些青蛙作为打发时间的游戏。她站在笔直的马路上，她的前方趴着 $N$ 只青蛙（可以看作一条直线上有 $N$ 只青蛙），这些青蛙的编号从近到远依次为 $1,2,\cdots,N$ 。每只青蛙的初始位置与佩奇的距离是已知的，从近到远分别为 $A_1, A_2, \cdots, A_N$。可能有多只青蛙与佩奇的距离相同。佩奇从最初的位置一直向前走，经过奇数只青蛙的时候会逗弄一下这只青蛙，这只青蛙受到惊吓会向前跳 $D$ 米，路过偶数只青蛙的时候什么也不做（没有被逗弄的青蛙不会移动）。重复这个过程直到佩奇前方没有青蛙，到此游戏结束。
需要注意一只青蛙向前跳跃后，佩奇继续往前走还会遇到它，由于佩奇记不清前面是否已遇到过这只青蛙，这只青蛙会被当成尚未遇见的并重复计数，因此一只青蛙可能会被逗弄多次。当佩奇经过的一个位置同时趴着多只青蛙时，佩奇会将这些青蛙按照初始编号排序，初始编号小的看做离自己更近。
现在佩奇想要知道游戏结束时，离佩奇初始位置最远的青蛙与佩奇初始位置的距离是多少。
输入格式
输入共两行。
第一行包含 $2$ 个由空格分隔的正整数，分别表示青蛙的数量 $N(1\leq N\leq 10^5)$ 和青蛙受到惊吓后跳跃的距离 $D(1\leq D\leq 10^9)$。第二行包含 $N$ 个由空格分隔的正整数，从左到右分别为 $A_1, A_2, \cdots, A_N(1\leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9)$，分别表示 $N$ 只青蛙的初始位置与佩奇初始位置的距离。
输出格式
输出是一个整数，表示游戏结束时，离佩奇初始位置最远的青蛙与佩奇初始位置的距离。
样例
Input
3 5 2 5 8
Output
17
Input
4 3 2 2 4 6
Output
12
提示
样例#1 总共有 3 只青蛙，一只青蛙受惊吓后会向前跳跃 5 米，初始状态下青蛙离佩奇的初始位置距离分别为 2、5、8 米。 初始青蛙位置: 2 5 8。
佩奇向前走，第 1 次经过的青蛙位置为 2，她逗弄了这只青蛙，青蛙受到惊吓向前跳跃了 5 米，位置变为 7，另外 2 只青蛙位置不变，第一次逗弄后佩奇初始位置从近到远的青蛙位置变为：5 7 8。
佩奇继续向前走，第 2 次经过的青蛙位置为 5，她什么也没有做，青蛙位置不变。
佩奇第 3 次经过的青蛙位置为 7，她逗弄了这只青蛙，青蛙受到惊吓向前跳跃了 5 米，位置变为 12。3 只青蛙位置变为：5 8 12。
第 4 次经过的青蛙位置为 8，她什么也没有做。
佩奇第 5 次经过的青蛙位置为 12，她逗弄了这只青蛙，青蛙向前跳跃了 5 米，位置变为 17。3 只青蛙位置变为：5 8 17。
第 6 次经过的青蛙位置为 17，她什么也没有做。
至此，佩奇前方没有青蛙了，游戏结束，当前位置为 17 的青蛙离佩奇初始位置最远。
创建: 1 年，7 月前.
修改: 1 年，7 月前.
最后提交: 3 月前.
来源: N/A
题目标签