Ghép đội (Team Pairing)

Phiên bản: Phước Hưng OJ

Đề bài

Có $N$ học sinh. Học sinh thứ $i$ có mức năng lực $A_i$. Mỗi đội gồm đúng hai học sinh khác nhau. Hai học sinh $i$ và $j$ có thể lập thành một đội nếu

Mỗi học sinh được tham gia nhiều nhất một đội. Hãy tìm số đội nhiều nhất có thể lập.

Input

• Dòng đầu chứa hai số nguyên $N$ và $D$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In ra một số nguyên duy nhất là số đội lớn nhất có thể lập.

Subtask

• Subtask 1 (40%): $1\le N\le 20$, $0\le D\le 10^9$, $|A_i|\le 10^9$.
• Subtask 2 (30%): $1\le N\le 2000$, $0\le D\le 10^9$, $|A_i|\le 10^9$.
• Subtask 3 (30%): $1\le N\le 2\times10^5$, $0\le D\le 10^9$, $|A_i|\le 10^9$.

Ví dụ

Ví dụ 1

Input

7 2
1 3 4 8 9 10 15

Output

2

Giải thích

Có thể tạo hai đội từ các cặp mức năng lực $(1,3)$ và $(8,9)$. Không thể tạo được $3$ đội.

Ví dụ 2

Input

6 0
5 5 5 1 1 2

Output

2

Giải thích

Với $D=0$, chỉ các học sinh có mức năng lực bằng nhau mới có thể ghép. Có thể tạo một đội từ hai học sinh có năng lực $5$ và một đội từ hai học sinh có năng lực $1$.