Description

一条马路上趴着很多青蛙，佩奇正好非常无聊，打算逗弄一下这些青蛙作为打发时间的游戏。她站在笔直的马路上，她的前方趴着 N 只青蛙（可以看作一条直线上有N只青蛙），这些青蛙的编号从近到远依次为 1,2,⋯,N 。每只青蛙的初始位置与佩奇的距离是已知的，从近到远分别为 $A_1$,$A_2$,...$A_n$ 。可能有多只青蛙与佩奇的距离相同。佩奇从最初的位置一直向前走，经过奇数只青蛙的时候会逗弄一下这只青蛙，这只青蛙受到惊吓会向前跳 D 米，路过偶数只青蛙的时候什么也不做（没有被逗弄的青蛙不会移动）。重复这个过程直到佩奇前方没有青蛙，到此游戏结束。

需要注意一只青蛙向前跳跃后，佩奇继续往前走还会遇到它，由于佩奇记不清前面是否已遇到过这只青蛙，这只青蛙会被当成尚未遇见的并​重复计数​，因此​一只青蛙可能会被逗弄多次​。当佩奇经过的一个位置同时趴着多只青蛙时，佩奇会将这些青蛙​按照初始编号排序，初始编号小的看做离自己更近​。

现在佩奇想要知道游戏结束时，离佩奇初始位置最远的青蛙与佩奇初始位置的距离是多少。

Format

Input

输入共两行。

第一行包含 2 个由空格分隔的正整数，分别表示青蛙的数量 N(1≤N≤$10^5$) 和青蛙受到惊吓后跳跃的距离 D(1≤D≤$10^9$)。第二行包含 N 个由空格分隔的正整数，从左到右分别为$A_1$,$A_2$,...$A_N$ (1≤$A_1$,≤$A_2$,≤⋯≤$A_N$≤$10^9$,)，分别表示 N 只青蛙的初始位置与佩奇初始位置的距离。 .

Output

输出是一个整数，表示游戏结束时，离佩奇初始位置最远的青蛙与佩奇初始位置的距离。

Samples

input1

3 5
2 5 8

output1

17

input2

4 3
2 2 4 6

output2

12

Prompt

样例#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 的青蛙离佩奇初始位置最远。

Limitation

1s, 100024KiB for each test case.