Đề thi thử vào 10 chuyên Lam Sơn câu 2

ĐỀ BÀI: CHIA NHÓM (ĐỀ THI THỬ VÀO 10 CHUYÊN LAM SƠN 2023 - CÂU 2)

Trường THPT LS có \(N\) bạn học sinh, mỗi bạn có một chỉ số IQ (chỉ số thông minh). Để việc học tập của các bạn được thuận lợi, nhà trường quyết định chia \(N\) bạn học sinh này thành các nhóm thoả mãn yêu cầu sau: Các bạn trong mỗi nhóm phải cùng giới tính và có chỉ số IQ bằng nhau. Nếu nhóm có 1 bạn thì vẫn được tính là 1 nhóm.

Yêu cầu: Các bạn hãy giúp nhà trường chia \(N\) bạn học sinh thành ít nhóm nhất thoả mãn điều kiện trên.

Dữ liệu vào (Input):

• Dòng đầu tiên là số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên mô tả thông tin của một học sinh: Số đầu tiên là 0 nếu giới tính là nữ, là 1 nếu giới tính là nam; số thứ hai là một số nguyên dương \(X\) là chỉ số thông minh (\(1 \le X \le 2 \times 10^9\)).

Kết quả ra (Output):

• Ghi ra một số nguyên dương duy nhất là số nhóm chia được.

Ví dụ:

Input

4
0 1
1 2
1 2
1 3

Output

3