예시로 학습하기

농부 존은 소 떼의 기록만 보고 얼룩이 있는지 없는지를 자동으로 맞히는 분류기를 만들려고 한다. 그런데 존이 남긴 기록은 부실해서, 소 $N$마리에 대해 아는 것은 몸무게와 얼룩 유무뿐이다. 소의 몸무게는 모두 서로 다르다.

분류기는 최근접 이웃 방식으로 동작한다. 새로 온 소 $C$의 얼룩 유무를 맞힐 때, 존은 자기 소 떼에서 $C$와 몸무게 차이가 가장 작은 소 $C'$를 찾는다. $C'$에 얼룩이 있으면 $C$에도 얼룩이 있다고 예측하고, $C'$에 얼룩이 없으면 얼룩이 없다고 예측한다. 몸무게 차이가 가장 작은 소가 하나로 정해지지 않고 두 마리가 같은 차이로 비기면, 그 두 마리 중 한 마리라도 얼룩이 있으면 $C$에 얼룩이 있다고 예측한다.

이제 농장에 막 도착한 소 떼로 이 분류기를 시험한다. 무게를 재 보니 $A$ 이상 $B$ 이하의 모든 정수 몸무게마다 소가 정확히 한 마리씩 있었다. 이 가운데 얼룩이 있다고 분류되는 소가 몇 마리인지 구하라. 분류기는 기존 소 $N$마리의 기록만 쓰고, 새로 온 소의 정보는 쓰지 않는다. $A$와 $B$가 매우 클 수 있으므로 $A$부터 $B$까지 1씩 늘려 가며 세는 방법은 제한 시간 안에 끝나지 않는다.

첫째 줄에 정수 $N$, $A$, $B$가 주어진다. ($1 \le N \le 50000$, $1 \le A \le B \le 10^9$)

다음 $N$개의 줄에는 소 한 마리의 정보가 주어진다. 얼룩이 있는 소는 S W, 얼룩이 없는 소는 NS W 형식이고, $W$는 그 소의 몸무게다. 몸무게는 모두 $1$ 이상 $10^9$ 이하의 정수이며 서로 다르다.

분류기가 얼룩이 있다고 판정하는 새 소의 수를 한 줄에 출력한다.