Bài 3. Phần thưởng (4,0 điểm; Đề HSG9 tỉnh Đắk Lắk 2025-2026)

Sau khi đạt kết quả cao tại kỳ thi học sinh giỏi THCS cấp tỉnh, bố An có N phần thưởng dành cho An, phần thưởng thứ i có giá trị A_i, bố đặt các phần thưởng theo thứ tự giá trị không giảm để An tự chọn các phần thưởng tùy ý, nhưng với điều kiện giá trị chênh lệch giữa 2 phần thưởng lớn nhất và nhỏ nhất không vượt quá K.

Dữ liệu vào: Đọc dữ liệu từ bàn phím với cấu trúc như sau:

• Dòng đầu tiên gồm 2 số nguyên dương N và K (N ≤ 10⁷; K ≤ 10⁹).
• Dòng thứ 2 gồm số N số nguyên A_i là giá trị các phần thưởng (A_i ≤ 10⁹).

Dữ liệu ra: In ra màn hình số nguyên dương duy nhất là số lượng phần thưởng tối đa mà An có thể nhận.
Ví dụ:

Giải thích:

• An có thể nhận 4 phần thưởng có giá trị là 1 2 5 7 là nhiều nhất có thể.

Giới hạn:

• 50% số test tương ứng với 50% số điểm thỏa mãn 1 ≤ N ≤ 3000.
• 30% số test tương ứng với 30% số điểm thỏa mãn 3000 ≤ N ≤ 5 × 10⁶.
• 20% số test tương ứng với 20% số điểm không có ràng buộc gì thêm.