Chọn cặp


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Hưởng ứng phong trào thi đua học tập của trường, cô giáo chủ nhiệm lớp của Nam muốn chọn các cặp đôi bạn giúp đỡ nhau cùng tiến. Lớp của Nam có $n$ học sinh, được đánh số từ 1 đến $n$, học sinh thứ $i$ có chỉ số học lực $a_i$. Để có được sự cân bằng giữa các cặp bạn cùng tiến, cô giáo muốn chọn các cặp bạn có tổng chỉ số học lực đôi một giữa các cặp chênh lệch nhau không quá một giá trị nhỏ hơn $d$ sao cho mỗi bạn xuất hiện trong không quá một cặp. Cô giáo mong muốn chọn được nhiều cặp như vậy nhất.

Cho biết số học sinh của lớp và chỉ số học lực của từng học sinh, hãy tính số cặp bạn cùng tiến nhiều nhất mà có tổng chỉ số học lực đôi một giữa các cặp chênh lệch nhau không quá $d$.

Dữ liệu

  • Dòng đầu tiên chứa hai số nguyên $n,d \ (2\le n\le 2000; 0\le d\le 1)$.
  • Dòng tiếp theo chứa $n$ số nguyên dương $a_i \ (0<a_i\le10^9)$.

Kết quả

  • Số cặp nhiều nhất tìm được.

Chấm điểm

20;$n\le10; d=0$. 20;$n\le200; d=0$. 20;$n\le2000; d=0$. 30;$n\le200; d=1$. 10;$n\le2000; d=1$.

Ví dụ

Ví dụ 1

input

7 1
9 1 2 4 5 6 8

output

3

Comments

There are no comments at the moment.