Nhân dịp chào đón Giáng sinh, Thành quyết định lấy hết tiền học bổng của mình để mua toàn bộ N món quà lưu niệm tặng các bạn nữ trong lớp, các món quà được đánh số từ 1 đến N, món thứ i có giá là a_i, i = 1÷N. Cảm động trước hành động của Thành, chủ cửa hàng đã có chương trình khuyến mãi đặc biệt dành cho em. Thành được phép chia N món quà thành một hay nhiều đơn hàng với điều kiện hai món quà bất kì trong một đơn phải có giá chênh lệch nhau không bé hơn K. Với mỗi đơn hàng như vậy, Thành chỉ phải thanh toán số tiền là giá của món quà đắt nhất trong đơn đó mà thôi.

Yêu cầu: Giúp Thành chia N món quà thành các đơn hàng sao cho tổng số tiền phải trả cho tất cả đơn hàng là nhỏ nhất.

Dữ liệu vào:

+ Dòng thứ nhất chứa hai số nguyên dương N và K  (N ≤ 10⁵, K ≤ 10⁹).

+ Dòng thứ hai gồm N số nguyên dương a₁, a₂,..., a_N (a_i ≤ 10⁹ với mọi i = 1÷N).

Kết quả: 

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

Ví dụ:

Ràng buộc:

+ Có 50% số test ứng với 50% số điểm có N ≤ 10⁴;

+ Có 50% số test còn lại ứng với 50% số điểm không có ràng buộc gì thêm.