p02130 Combine Two Elements_36605
Problem

Given $ N $ a pair of non-negative integers $ (a_i, b_i) $ and non-negative integers $ A $, $ B $.
I want to do as many of the following operations as possible.


* $ | a_i --b_i | \ leq A $ or $ B \ leq | a_i --b_i | \ leq Take out and delete the element $ i $ that satisfies 2A $
* $ | (a_i + a_j)-(b_i + b_j) | \ leq A $ or $ B \ leq | (a_i + a_j)-(b_i + b_j) | Extract and delete the pair of j $ ($ i \ neq j $)

Find the maximum number of operations.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq N \ leq 800 $
* $ 0 \ leq A, B \ leq 10 ^ 5 $
* $ 0 \ leq a_i, b_i \ leq 10 ^ 5 $
* $ A \ leq B $ and $ B \ leq 2A $

Input

The input is given in the following format.


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


All inputs are given as integers.
$ N $, $ A $, $ B $ are given on the first line, separated by blanks.
The $ i $ th pair $ a_i $ and $ b_i $ ($ 1 \ leq i \ leq N $) are given in the second and subsequent $ N $ lines, separated by blanks.

Output

Output the maximum number of operations on one line.

Examples

Input

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


Output

4


Input

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


Output

5
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;


////フォード - ファルカーソン法 O(Flow|E|)

typedef int Weight;

const Weight INF = 1e9;
const Weight ZERO = 0;
struct Edge {
	int src, dst;
	Weight weight;
	int rev;
	int id;
	Edge(int src_, int dst_, Weight weight_, const int rev_, const int id_) :
		src(src_), dst(dst_), weight(weight_), rev(rev_), id(id_) { }
	Edge(int src_, int dst_, Weight weight_, const int rev_) :
		src(src_), dst(dst_), weight(weight_), rev(rev_) { }
	Edge() :src(0), dst(0), weight(0) {
	}
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph&g, int from, int to, int cap)
{
	g[from].push_back(Edge(from, to, cap, (int)g[to].size()));
	g[to].push_back(Edge(to, from, 0, (int)g[from].size() - 1));
}
//二つを繋ぐ線を完全に消す
void erase_edge(Graph&g, const  int from, const int to) {
	g[from].erase(remove_if(g[from].begin(), g[from].end(), [=](const Edge&e) {return e.dst == to; }), g[from].end());
	g[to].erase(remove_if(g[to].begin(), g[to].end(), [=](const Edge&e) {return e.dst == from; }), g[to].end());
}
int dfs(vector<int>&used, Graph&g, int now, int t, int f)
{
	if (now == t) {
		return f;
	}
	used[now] = true;
	for (int i = 0; i<g[now].size(); ++i) {
		Edge &e = g[now][i];
		if (!used[e.dst] && e.weight>0) {
			int d = dfs(used, g, e.dst, t, min(f, e.weight));
			if (d > 0) {
				e.weight -= d;
				g[e.dst][e.rev].weight += d;
				return d;
			}
		}
	}
	return 0;
}
Weight fold_falc(Graph g, const int start, const int goal) {
	Weight ans = 0;
	while (1) {
		vector<int>used(g.size());
		int flow = dfs(used, g, start, goal, INF);
		if (!flow)return ans;
		else ans += flow;
	}
}

int main() {
	int N,A,B;cin>>N>>A>>B;
	vector<vector<int>>sas(2);
	int ans=0;
	for (int i = 0; i < N; ++i) {
		int a, b;cin>>a>>b;
		int num=a-b;
		if ( abs(num)<=A || (B <= abs(num) && abs(num) <= 2 * A)) {
			ans++;
		}
		else {
			if(num>0)sas[0].push_back(num);
			else sas[1].push_back(-num);
		}
	}
	const int start=0;
	const int zero=1;
	const int one=zero+sas[0].size();
	const int goal=one+sas[1].size();
	Graph g(goal+1);

	for (int i = 0; i < sas[0].size(); ++i) {
		add_edge(g,start,zero+i,1);
	}
	for (int i = 0; i < sas[0].size(); ++i) {
		for (int j = 0; j < sas[1].size(); ++j) {
			int x=zero+i;
			int y=one+j;
			int num=sas[0][i]-sas[1][j];

			if ( abs(num)<=A || (B <= (abs(num)) && (abs(num)) <= 2 * A)) {
				add_edge(g,x,y,1);
			}
		}
	}
	for (int i = 0; i < sas[1].size(); ++i) {
		add_edge(g, one+i, goal, 1);
	}

	ans+=fold_falc(g,start,goal);
	cout<<ans<<endl;
	return 0;
}

10 7 12
34 70
36 0
12 50
76 46
33 45
61 21
0 1
24 3
98 41
23 84 5 3 5
7 2
13 1
1 1
2 9
2 4 10 7 12
34 70
36 0
12 50
76 46
33 45
61 21
0 0
24 3
98 41
23 84 5 3 4
7 2
13 1
1 1
2 9
2 4 10 7 12
34 70
36 0
12 50
19 46
33 45
61 21
0 0
24 3
98 41
23 84 2 3 4
7 3
13 1
1 1
2 9
2 4 2 3 5
7 3
13 1
1 1
2 9
2 4 10 1 12
34 70
36 0
12 50
19 46
33 45
61 21
0 0
24 3
98 73
23 84 6 1 0
18 9
90 -3
2 11
1 0
2 1
23 31
-14 1
1 12
36 24
4 11 5 3 4
7 3
13 1
1 1
2 9
2 4 10 7 12
34 70
36 0
12 50
19 46
33 45
61 21
0 0
24 3
98 73
23 84 10 5 12
34 70
36 0
12 50
19 46
33 45
61 21
0 0
24 3
98 73
23 84 2 3 5
7 3
13 1
1 1
2 7
2 4 10 1 12
34 70
36 0
12 50
19 46
33 45
61 21
0 0
24 5
98 73
23 84 2 3 5
7 3
13 1
1 2
2 7
2 4 10 1 12
34 70
36 0
12 29
19 46
33 45
61 21
0 0
24 5
98 73
23 84 2 3 5
7 3
13 1
1 2
1 7
2 4 10 1 12
34 70
36 0
12 29
19 46
33 45
61 21
0 0
42 5
98 73
23 84 2 3 5
7 3
13 1
1 4
1 7
2 4 10 1 12
34 70
36 0
12 29
19 46
33 20
61 21
0 0
42 5
98 73
23 84 2 3 7
7 3
13 1
1 4
1 7
2 4 10 1 12
34 70
36 0
12 29
26 46
33 20
61 21
0 0
42 5
98 73
23 84 1 3 7
7 3
13 1
1 4
1 7
2 4 10 1 12
34 70
36 0
12 29
26 46
33 20
61 10
0 0
42 5
98 73
23 84 1 3 7
7 3
13 1
1 4
1 7
2 3 10 1 12
34 70
36 0
12 29
26 46
33 20
58 10
0 0
42 5
98 73
23 84 1 3 7
7 3
13 1
1 4
0 7
2 3 10 1 12
22 70
36 0
12 29
26 46
33 20
58 10
0 0
42 5
98 73
23 84 1 3 7
7 0
13 1
1 4
0 7
2 3 10 1 12
22 70
36 0
12 29
26 46
33 20
58 15
0 0
42 5
98 73
23 84 1 3 7
0 0
13 1
1 4
0 7
2 3 10 1 12
22 70
36 0
12 29
26 46
33 20
58 15
0 0
42 5
98 44
23 84 1 3 7
0 0
13 2
1 4
0 7
2 3 10 1 12
22 70
36 0
12 43
26 46
33 20
58 15
0 0
42 5
98 44
23 84 1 6 7
0 0
13 2
1 4
0 7
2 3 10 1 12
22 70
36 0
12 43
26 46
33 20
58 10
0 0
42 5
98 44
23 84 1 6 7
0 0
13 2
1 6
0 7
2 3 10 1 12
22 70
36 -1
12 43
26 46
33 20
58 10
0 0
42 5
98 44
23 84 2 6 7
0 0
13 2
1 6
0 7
2 3 10 1 12
22 70
36 -1
12 43
26 46
33 20
58 10
0 0
80 5
98 44
23 84 2 6 7
0 0
13 2
1 6
0 8
2 3 10 1 12
22 70
36 -1
12 43
26 46
33 20
58 10
0 0
80 5
98 32
23 84 2 6 7
1 0
13 2
1 6
0 8
2 3 10 1 12
15 70
36 -1
12 43
26 46
33 20
58 10
0 0
80 5
98 32
23 84 2 6 7
1 0
13 2
1 6
0 14
2 3 10 1 12
15 70
36 -1
18 43
26 46
33 20
58 10
0 0
80 5
98 32
23 84 2 6 0
1 0
13 2
1 6
0 14
2 3 10 1 12
15 70
36 -1
18 43
26 46
33 20
58 10
0 -1
80 5
98 32
23 84 2 6 0
1 0
13 2
1 8
0 14
2 3 10 1 12
15 70
36 -1
18 43
26 46
33 20
58 10
0 -1
80 5
98 32
23 30 2 6 0
1 0
16 2
1 8
0 14
2 3 10 1 12
15 70
58 -1
18 43
26 46
33 20
58 10
0 -1
80 5
98 32
23 30 2 6 0
0 0
16 2
1 8
0 14
2 3 10 1 12
15 70
58 -1
18 43
26 84
33 20
58 10
0 -1
80 5
98 32
23 30 2 6 0
0 0
16 2
1 8
0 13
2 3 10 1 12
15 70
58 -1
18 43
26 84
33 20
58 10
0 -1
80 5
98 35
23 30 2 6 0
0 0
16 2
2 8
0 13
2 3 10 1 12
15 70
58 -1
18 43
26 40
33 20
58 10
0 -1
80 5
98 35
23 30 2 6 0
0 0
16 2
2 8
1 13
2 3 10 1 12
15 70
58 -1
18 43
26 40
33 20
58 10
0 -1
80 5
98 35
23 10 2 6 0
0 0
16 2
4 8
1 13
2 3 10 1 12
15 70
58 -1
18 43
26 40
33 20
58 10
0 -1
80 5
29 35
23 10 2 6 0
0 0
16 2
4 12
1 13
2 3 10 1 3
15 70
58 -1
18 43
26 40
33 20
58 10
0 -1
80 5
29 35
23 10 2 7 0
0 0
16 2
4 12
1 13
2 3 10 1 3
14 70
58 -1
18 43
26 40
33 20
58 10
0 -1
80 5
29 35
23 10 2 7 0
0 0
16 0
4 12
1 13
2 3 10 1 3
14 70
58 -1
18 43
26 40
3 20
58 10
0 -1
80 5
29 35
23 10 2 4 0
0 0
16 0
4 12
1 13
2 3 10 1 3
14 70
58 -1
18 43
26 40
3 1
58 10
0 -1
80 5
29 35
23 10 2 4 0
0 0
16 0
0 12
1 13
2 3 6 1 3
14 70
58 -1
18 43
26 40
3 1
58 10
0 -1
80 5
29 35
23 10 2 4 0
0 0
16 0
0 12
0 13
2 3 6 1 3
14 70
58 -1
6 43
26 40
3 1
58 10
0 -1
80 5
29 35
23 10 2 4 0
0 0
16 0
-1 12
0 13
2 3 6 1 3
14 70
58 -1
6 26
26 40
3 1
58 10
0 -1
80 5
29 35
23 10 2 4 0
-1 0
16 0
-1 12
0 13
2 3 6 1 3
14 70
58 -1
6 26
26 40
3 1
58 10
0 -1
80 5
44 35
23 10 2 4 0
-1 0
16 0
-1 12
1 13
2 3 6 1 3
14 70
58 -1
6 26
26 40
3 1
58 20
0 -1
80 5
44 35
23 10 2 4 0
-1 0
16 0
-1 12
1 13
2 5 6 1 3
14 70
108 -1
6 26
26 40
3 1
58 20
0 -1
80 5
44 35
23 10 2 4 0
-1 0
7 0
-1 12
1 13
2 5 6 1 3
14 70
108 -1
6 26
26 40
3 1
58 20
0 -1
50 5
44 35
23 10 2 4 0
-1 0
7 0
0 12
1 13
2 5 6 1 3
14 70
108 -1
9 26
26 40
3 1
58 20
0 -1
50 5
44 35
23 10 2 4 0
-1 1
7 0
0 12
1 13
2 5 6 1 3
14 70
108 -1
9 26
26 40
3 1
58 30
0 -1
50 5
44 35
23 10 2 4 1
-1 1
7 0
0 12
1 13
2 5 6 1 3
14 70
108 -1
9 26
26 40
3 1
58 31
0 -1
50 5
44 35
23 10 2 4 1
-1 1
7 0
0 9
1 13
2 5 6 1 3
14 70
108 -1
9 26
26 40
3 1
58 31
0 -1
50 5
44 58
23 10 2 4 1
-1 1
7 0
0 9
0 13
2 5 6 1 3
14 70
108 -1
9 26
26 40
3 1
58 31
0 -1
50 5
47 58
23 10 2 4 0
-1 1
7 0
0 9
1 13
2 5 6 1 3
14 70
108 -1
9 26
26 40
3 1
58 31
0 -1
50 5
92 58
23 10 2 4 0
-1 1
7 0
0 9
1 5
2 5 6 1 3
14 70
108 -1
9 12
26 40
3 1
58 31
0 -1
50 5
92 58
23 10 2 4 0
-1 1
7 1
0 9
1 5
2 5 6 1 3
14 70
108 -1
9 12
26 40
3 1
58 31
-1 -1
50 5
92 58
23 10 2 4 0
-1 1
7 2
0 9
1 5
2 5 6 1 3
14 70
108 -1
9 12
26 40
3 1
58 31
-1 -1
22 5
92 58
23 10
5 4 5
 4
 6
 1
 0
 2
 3
 4
 5
 4
 0
 2
 0
 2
 0
 2
 0
 2
 0
 2
 0
 2
 0
 2
 0
 2
 0
 1
 1
 1
 1
 1
 1
 2
 1
 2
 2
 2
 2
 2
 2
 1
 2
 1
 2
 1
 2
 1
 1
 1
 1
 2
 1
 2
 1
 2
 1
 2
 1
 2
 1
 2
 2
 2
 1
 2
 1
 2
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 1
 0
 2
 0
 2
 0
 2
 0
 2
 0
 2
 0
 2
 0
 2
 0
 2
 1
 2
 1
 2
 1
