In 2086, it was decided to add tug-of-war on ice to the program of the Winter Olympics. To hold the final of the competition, the organizers found n pieces of rope. To increase the entertainment of the competition, it was decided to tie some of these pieces into one rope as long as possible.
When the tying work began, it turned out that the knot connecting two pieces of rope to each other takes d centimeters of rope from each of the tied ends. Also, it turned out that it is impossible to connect so that the resulting nodes are close to each other: the distance between neighboring nodes must be at least d centimeters. For example, if d \u003d 10, then after tying pieces of rope 25 and 50 centimeters long, a rope 55 centimeters long is obtained, 15 centimeters from one of the edges of which there is a knot.
There is little time left before the start of the competition, so they turned to you for help. Help the organizers figure out the maximum rope length they can get.
Input data format
The first line contains numbers n (1 ≤ n ≤ 100 000) and d (1 ≤ d ≤ 1000) — the number of pieces of rope and the length of the rope required to tie a knot. The second line contains n numbers ai (1 ≤ a
i ≤ 1000) — available lengths of rope.
Output data format
Print a single number — the maximum rope length that can be obtained.
|
Enter |
Output |
2 10
25 50
|
55 |
5 2
4 5 6 7 8
|
14 |