Learning by Example

Farmer John wants a classifier that guesses from his herd records alone whether a cow has spots. His records are thin: for each of his $N$ cows he knows only the weight and whether that cow has spots. All weights are distinct.

The classifier uses nearest neighbours. To guess whether a new cow $C$ has spots, John finds the cow $C'$ in his herd whose weight is closest to the weight of $C$. If $C'$ has spots, he guesses that $C$ has spots; if $C'$ has no spots, he guesses that $C$ has none. If the closest weight is not achieved by a single cow but two cows tie, he guesses that $C$ has spots when at least one of those two has spots.

John now tests the classifier on a group of cows that has just arrived at his farm. After weighing them he sees exactly one cow of every integer weight between $A$ and $B$ inclusive. Determine how many of these cows the classifier labels as spotted. The classifier uses only the records of the $N$ existing cows, never the data of the new ones. $A$ and $B$ can both be large, so a loop that walks from $A$ to $B$ one weight at a time will not finish inside the time limit.

The first line contains three integers $N$, $A$, and $B$ ($1 \le N \le 50000$, $1 \le A \le B \le 10^9$).

Each of the next $N$ lines describes one cow. A spotted cow of weight $W$ is written as S W, and a cow with no spots as NS W. All weights are distinct integers with $1 \le W \le 10^9$.

Print on one line the number of new cows that the classifier labels as spotted.