Búp bê

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
phudung8xgmail
Dạng bài
Điểm: 200 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 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 ai. 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ì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 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.

Input

Gồm 2 dòng

  • Dòng 1 chứa hai số nguyên dương \(n ≤ 10^5\); \(k ≤ 10^9\) cách nhau một khoảng trắng.

  • Dòng 2 chứa n số nguyên dương \(a_1, a_2, ..., a_n\) ( \(a_i ≤ 10^9\)), mỗi số cách nhau một khoảng trắng.

Output

  • Là 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.

Example

Test 1

Input 
8 2
8 4 2 1 1 3 5 9
Output 
18

Bình luận