Problem:

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



Sample input:
5 3 5
7 2
13 1
1 1
2 9
2 4


Sample output:
4

Submission status: Accepted

Solution code:
N, A, B = map(int, input().split())
P = []
Q = []
ans = 0
for i in range(N):
    a, b = map(int, input().split())
    v = abs(a-b)
    if v <= A or B <= v <= 2*A:
        ans += 1
        continue
    if a > b:
        P.append(a-b)
    else:
        Q.append(a-b)

import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

dinic = Dinic(2+len(P)+len(Q))
LP = len(P)
for i in range(len(P)):
    dinic.add_edge(0, 2+i, 1)
for j in range(len(Q)):
    dinic.add_edge(2+LP+j, 1, 1)
for i, p in enumerate(P):
    for j, q in enumerate(Q):
        v = abs(p+q)
        if v <= A or B <= v <= 2*A:
            dinic.add_edge(2+i, 2+LP+j, 1)
ans += dinic.max_flow(0, 1)
print(ans)