New Game AI

Time Limit : 2 sec, Memory Limit : 262144 KB

Problem J New Game AI

Aoba is a beginner programmer who works for a game company. She was appointed to develop a battle strategy for the enemy AI (Artificial Intelligence) in a new game. In this game, each character has two parameters, hit point ($hp$) and defence point ($dp$). No two characters have the same $hp$ and $dp$ at the same time. The player forms a party by selecting one or more characters to battle with the enemy. Aoba decided to develop a strategy in which the AI attacks the weakest character in the party: that is, the AI attacks the character with the minimum hit point in the party (or, if there are several such characters, the character with the minimum defense point among them). She wrote a function selectTarget($v$) that takes an array of characters representing a party and returns a character that her AI will attack.

However, the project manager Ms. Yagami was not satisfied with the behavior of her AI. Ms. Yagami said this AI was not interesting.

Aoba struggled a lot, and eventually she found that it is interesting if she substitutes one of the constant zeros in her program with a constant $C$. The rewritten program is as follows. Note that Character is a type representing a character and has fields $hp$ and $dp$ which represent the hit point and the defense point of the character respectively.

int C = <constant integer>;

Character selectTarget(Character v[]) {
  int n = length(v);
  int r = 0;
  for (int i = 1; i < n; i++) {
    if (abs(v[r].hp - v[i].hp) > C) {
      if (v[r].hp > v[i].hp) r = i;
    } else {
      if (v[r].dp > v[i].dp) r = i;
  return v[r];

By the way, this function may return different characters according to the order of the characters in $v$, even if $v$ contains the same set of characters. Ms. Yagami wants to know how many characters in a party may become the target of the new AI. Aoba's next task is to write a program that takes a given party $v$ and a constant $C$, and then counts the number of characters that may become the return value of selectTarget($v$) if $v$ is re-ordered.


The input consists of a single test case. The first line contains two integers $N$ $(1 \leq N \leq 50,000)$ and $C$ $(0 \leq C \leq 10^9)$. The first integer $N$ represents the size of $v$. The second integer $C$ represents the constant $C$ in Aoba's program. The i-th line of the following $N$ lines contains two integers $hp_i$ and $dp_i$ $(0 \leq hp_i, dp_i \leq 10^9)$. $hp_i$ represents the hit point of the $i$-th character in $v$, and $dp_i$ represents the defense point of the $i$-th character in $v$. You can assume that $hp_i \ne hp_j$ or $dpi \ne dp_j$ if $i \ne j$ for any $1 \leq i, j \leq N$.


Display the number of characters that may become the return value of selectTarget($v$), if $v$ is shuffled in an arbitrary order.

Sample Input 1

5 3
1 5
3 4
5 3
7 2
9 1

Output for the Sample Input 1


Sample Input 2

3 2
1 2
3 1
5 1

Output for the Sample Input 2


Sample Input 3

4 1
2 0
0 4
1 1
5 9

Output for the Sample Input 3


Sample Input 4

5 9
4 10
12 4
2 14
9 19
7 15

Output for the Sample Input 4


Source: Japan Alumni Group Spring Contest 2015 , Japan, 2015-04-19