4. 通过示例学习 (Learning by Example)

USACO 2014 十二月月赛, 铜组

Farmer John 一直在阅读关于机器学习这个激动人心的领域的资料，通过分析大量数据，人们可以学习到有趣且有时出乎意料的模式（他甚至开始把他农场里的一块地称为"机器学习田"！）。FJ 决定利用他现有牛群的数据来构建一个自动分类器，用于猜测一头牛是否有斑点。

不幸的是，FJ 在记录他的牛的数据方面做得不太好。对于他的 N 头牛（1 <= N <= 50,000），他只知道每头牛的体重，以及这头牛是否有斑点。每头牛的体重都是互不相同的。根据这些数据，他构建了一个所谓的"最近邻分类器"。为了猜测一头新牛 C 是否有斑点，FJ 首先在他的牛群中找到体重与 C 最接近的那头牛 C'。如果 C' 有斑点，那么 FJ 就猜测 C 也有斑点；如果 C' 没有斑点，FJ 就猜测 C 也没有斑点。如果不存在唯一的最接近的邻居 C'，而是有两头牛与 C 的体重差值相同且都是最小，那么 FJ 会这样猜测：如果这两头最近邻中有一头或两头都有斑点，他就猜测 C 有斑点。

FJ 想用一批刚到农场的新牛来测试他的新自动斑点预测器。在给这些牛称重后，他发现这批新到的牛包含了 A 到 B（包含端点）之间的每一个整数体重的牛。请确定这些牛中有多少会被 FJ 的新分类器归类为有斑点。注意，分类器仅使用 FJ 现有的 N 头牛的数据来做决策，不使用任何新牛的数据。另请注意，由于 A 和 B 都可能非常大，如果你的程序从 A 到 B 逐个循环计数，可能无法运行得足够快。

输入格式：（文件 learning.in）

输入的第一行包含三个整数 N、A 和 B（1 <= A <= B <= 1,000,000,000）。

接下来的 N 行每行描述一头牛。每行包含 S W（表示一头体重为 W 的有斑点的牛）或 NS W（表示一头体重为 W 的无斑点的牛）。所有体重都是 1 到 1,000,000,000 范围内的整数。

样例输入：

3 1 10
S 10
NS 4
S 1

输出格式：（文件 learning.out）

输出一个整数，表示 FJ 的算法将归类为有斑点的新来牛的数量。在示例中，体重为 1、2、7、8、9 和 10 的新来牛都将被归类为有斑点。

样例输出：

6