Công ty đồ chơi ~MrCat~ nhập khẩu ~n~ con búp bê gỗ. Các con búp bê được đánh số từ 1 tới ~n~ trong đó con búp bê thứ ~i~ là một hộp rỗng có kích thước là một số nguyên ~a_i~. Người ta có thể lồng con búp bê thứ ~i~ vào trong con búp bê thứ ~j~ nếu con búp bê thứ ~j~ đang rỗng và \(~a_i~ + k \leq ~a_j~\), với ~k~ là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty ~MrCat~ chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho.
Yêu cầu
Hãy giúp ~MrCat~ lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.
Dữ liệu
Dòng 1: Chứa hai số nguyên dương ~n, k~.
Dòng 2: Chứa ~n~ số nguyên dương ~a_1, a_2, … , a_n~.
Kết quả
Một số nguyên duy nhất là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.
Giới hạn
\(n \leq ~10^5~, k \leq ~10^9~, ∀i: ~a_i~ \leq ~10^9~\).
Input
8 2
8 4 2 1 1 3 5 9
Output
18
Bình luận