PDOLLS
Công ty đồ chơi X nhập khẩu n con búp bê gỗ. Các con búp bê được đánh số từ 1 đến n trong đó 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 ≤ 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 X chỉ cần đặ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 công ty X 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 ≤ 10^5,k ≤ 10^9;
Dòng 2: chứa n số nguyên dương a[1],a[2],…,a[n] (a[i] ≤ 10^9).
Kết quả:
- Gồm một dòng ghi một số nguyên là tổng kích thước các con búp bê ngoài cùng theo phương án tìm được.
Sample Input:
8 2
8 4 2 1 1 3 5 9Sample Output:
18
Comments
Này là búp bê Nga á tr;))
ủa chứ s má :))