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 \leq 10^6, k \leq 10^5\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(v_1, v_2, \dots, v_n\) (\(v_i \leq 10^9\)).

Output

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

Example

3 2
1 5 5

10

4 1
1 4 3 5

5

Scoring

• \(30\%\) số test thỏa mãn: \(n \leq 10^2\).
• \(30\%\) số test thỏa mãn: \(n \leq 10^4\).
• \(40\%\) số test không có ràng buộc gì thêm.