Farmer John đã đọc rất nhiều về lĩnh vực học máy đầy thú vị, nơi người ta có thể khám phá những quy luật thú vị và đôi khi bất ngờ bằng cách phân tích dữ liệu lớn (ông thậm chí còn bắt đầu gọi một trong những cánh đồng ở trang trại là “cánh đồng học máy”!). FJ quyết định dùng dữ liệu về đàn bò hiện có để xây dựng một bộ phân loại tự động có thể dự đoán một cô bò có đốm hay không.

Không may, FJ không giỏi theo dõi dữ liệu về đàn bò của mình. Với mỗi cô bò trong số \(N\) cô bò (\(1 \le N \le 50\,000\)), ông chỉ biết khối lượng của cô bò và cô bò đó có đốm hay không. Mỗi cô bò có một khối lượng khác nhau. Từ dữ liệu này, ông xây dựng một thứ gọi là “bộ phân loại láng giềng gần nhất”. Để dự đoán một cô bò mới \(C\) có đốm hay không, trước tiên FJ tìm cô bò \(C'\) trong đàn có khối lượng gần với khối lượng của \(C\) nhất. Nếu \(C'\) có đốm, FJ dự đoán \(C\) cũng có đốm; nếu \(C'\) không có đốm, FJ cũng dự đoán như vậy về \(C\). Nếu không tồn tại một láng giềng gần nhất \(C'\) duy nhất mà có hai cô bò của FJ cùng gần nhất, thì FJ dự đoán \(C\) có đốm nếu một hoặc cả hai láng giềng gần nhất này có đốm.

FJ muốn thử nghiệm bộ dự đoán đốm tự động mới trên một nhóm bò mới vừa đến trang trại. Sau khi cân những cô bò này, ông nhận thấy lô bò mới có một cô bò ứng với mỗi khối lượng nguyên từ \(A\) đến \(B\), kể cả hai đầu. Hãy xác định có bao nhiêu cô bò trong số này sẽ được bộ phân loại mới của FJ phân loại là có đốm. Lưu ý rằng bộ phân loại chỉ đưa ra quyết định dựa trên dữ liệu từ \(N\) cô bò hiện có của FJ, chứ không dựa trên bất kỳ cô bò mới nào. Cũng lưu ý rằng vì \(A\) và \(B\) đều có thể rất lớn, chương trình của bạn nhiều khả năng sẽ không đủ nhanh nếu lặp qua từng số từ \(A\) đến \(B\) để đếm.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(A\) và \(B\) (\(1 \le A \le B \le 1\,000\,000\,000\)).

\(N\) dòng tiếp theo, mỗi dòng mô tả một cô bò. Mỗi dòng chứa S W, biểu thị một cô bò có đốm với khối lượng \(W\), hoặc NS W, biểu thị một cô bò không có đốm với khối lượng \(W\). Các khối lượng đều là số nguyên trong khoảng từ 1 đến \(1\,000\,000\,000\).

Dữ liệu ra

In ra một số nguyên duy nhất là số bò mới mà thuật toán của FJ sẽ phân loại là có đốm.

Ví dụ

3 1 10
S 10
NS 4
S 1

6

Nguồn

USACO 2014 December Contest, Bronze — Learning by Example. Tác giả đề: Brian Dean, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=490