Học Máy (Bronze)

Có $N$ con bò hiện có, mỗi con có cân nặng phân biệt và được gán nhãn có đốm (S) hoặc không có đốm (NS). Cho một dãy con bò mới với cân nặng từ $A$ đến $B$ (bao gồm cả hai đầu), hãy phân loại từng con bò mới bằng thuật toán k-nearest neighbor với $k=1$:

• Tìm con bò hiện có có cân nặng gần nhất với con bò mới.
• Nếu có một con duy nhất gần nhất: phân loại theo nhãn của con đó.
• Nếu có hai con cùng khoảng cách gần nhất: phân loại là có đốm nếu ít nhất một trong hai có đốm.

Đếm số con bò mới (với cân nặng nguyên trong $[A,B]$) được phân loại là có đốm.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $N$, $A$, $B$.

• $N$ dòng tiếp theo, mỗi dòng có dạng S W hoặc NS W — nhãn và cân nặng của con bò thứ $i$.

Dữ liệu ra

Một số nguyên duy nhất — số con bò mới được phân loại là có đốm.

Ràng buộc

• $1\le N\le 50000$
• $1\le A\le B\le {10}^9$
• $1\le W_i\le {10}^9$, các cân nặng hiện có là phân biệt

Ví dụ