Tug of War

Time limit2sMemory limit512 MB

Summary

Given n rope pieces, joining two pieces consumes d from each end and adjacent knots must be at least d apart; maximize the total length of one resulting rope.

Level: Medium6 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

In 2086, tug of war on ice was added to the Winter Olympics program. To hold the final, the organizers found $n$ pieces of rope. To make the event more exciting, they decided to tie some of these pieces together into a single rope as long as possible.

When the tying began, it turned out that a knot joining two pieces of rope uses $d$ centimeters of rope from each of the two ends being joined. It also turned out that the pieces cannot be tied so that the resulting knots are close to each other: the distance between neighboring knots must be at least $d$ centimeters. For example, if $d = 10$ , then after tying pieces of rope 25 and 50 centimeters long, the result is a rope 55 centimeters long with a knot 15 centimeters from one of its ends.

Little time remains before the competition, so the organizers turned to you for help. Help the organizers find the maximum length of rope they can obtain.

Input

The first line contains $n$ ( $1 \le n \le 100\,000$ ) and $d$ ( $1 \le d \le 1000$ ), the number of rope pieces and the length of rope used to tie a knot.

The second line contains $n$ numbers $a_i$ ( $1 \le a_i \le 1000$ ), the lengths of the available rope pieces.

Output

Print a single number, the maximum length of rope that can be obtained.

Examples2

Example 1
Input
```
2 10
25 50
```
Expected output
```
55
```
Example 2
Input
```
5 2
4 5 6 7 8
```
Expected output
```
14
```