Sau đợt lũ lụt, nhiều học sinh miền núi không còn đồ dùng học tập để đến trường. An và nhóm bạn trong lớp quyết định quyên góp tiền tiết kiệm để mua ~n~ gói đồ dùng học tập ủng hộ cho các bạn học sinh nói trên. Các gói đồ dùng được đánh số từ ~1~ đến ~n~, gói thứ ~i~ có giá là ~v_i~. Thầy An và các bạn là người tốt, ông chủ cửa hàng đã áp dụng chương trình khuyến mãi đặc biệt dành cho các bạn. Ông cho phép nhóm bạn An chia ~n~ gói đồ dùng học tập trên thành một hoặc nhiều kiện hàng, mỗi kiện hàng gồm một hoặc nhiều gói. Đối với kiện hàng có nhiều hơn một gói thì giá chênh lệch giữa hai gói bất kỳ không bé hơn ~k~. Với mỗi kiện hàng chia được, nhóm bạn An chỉ phải thanh toán số tiền của gói đồ dùng học tập đắt nhất trong kiện hàng đó.

Yêu cầu: Hãy giúp nhóm bạn An chia ~n~ gói đồ dùng học tập thành các kiện hàng sao cho tổng số tiền phải trả là ít nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ ~(n \le 10^6, k \le 10^6)~.

• Dòng thứ hai gồm ~n~ số nguyên dương ~v_1, v_2, \ldots, v_n~ ~(v_i \le 10^9)~.

Output

Ghi ra một số nguyên duy nhất là tổng số tiền phải trả.

Scoring

Sample Input 1

3 2
1 5 5

Sample Output 1

10

Sample Input 2

4 1
1 4 3 5

Sample Output 2

5

Notes

Ví dụ 1: Các phương án có thể chia kiện hàng:

• ~(1); (5); (5)~: Số tiền phải trả ~11~;

• ~(1, 5); (5)~: Số tiền phải trả ~10~;

Tổng số tiền phải trả ít nhất là ~10~.

Ví dụ 2: Có nhiều phương án chia kiện hàng nhưng phương án chia thành ~1~ kiện hàng ~(1, 4, 3, 5)~ có tổng tiền phải trả ít nhất là ~5~.