Problem G: Combine Two Elements

Problem

$N$個の非負整数のペア$(a_i, b_i)$と非負整数$A$, $B$ が与えられる。
以下のいずれかの操作をできるだけたくさん行いたい。

• $|a_i - b_i| \leq A$ または $B \leq |a_i - b_i| \leq 2A$を満たす要素$i$を取り出し、削除する
• $|(a_i + a_j) - (b_i + b_j)| \leq A$ または $B \leq |(a_i + a_j) - (b_i + b_j)| \leq 2A$ を満たす要素$i$と要素$j$ ($i \neq j$)の組を取り出し、削除する

最大の操作回数を求めよ。

Input

入力は以下の形式で与えられる。

$N$ $A$ $B$
$a_1$ $b_1$
$a_2$ $b_2$
...
$a_N$ $b_N$

入力はすべて整数で与えられる。
1行目に$N$,$A$,$B$が空白区切りで与えられる。
2行目以降の$N$行に$i$個目のペア$a_i$と$b_i$($1 \leq i \leq N$)が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $1 \leq N \leq 800 $
• $0 \leq A, B \leq 10^5 $
• $0 \leq a_i, b_i \leq 10^5$
• $A \leq B$ かつ $B \leq 2A$

Output

最大の操作回数を1行に出力せよ。

Sample Input 1

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

Sample Output 1

4

(7,2)を選んで削除する。
(1,1)を選んで削除する。
(2,4)を選んで削除する。
(13, 1)と(2, 9)を選んで削除する。
以上のように操作すると４回操作することができ、これが最大となる。

Sample Input 2

10 7 12
34 70
36 0
12 50
76 46
33 45
61 21
0 1
24 3
98 41
23 84

Sample Output 2

5

Note

Link

 

---