p02130 Combine Two Elements_36607
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
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	@SuppressWarnings("unchecked")
	int solve(int N, int[][] cap, int s, int t) {
		int tot = 0;
		int[][] flow = new int[N][N];
		while (true) {
			int[] pre = new int[N];
			Arrays.fill(pre, -1);
			ArrayDeque<Integer> que = new ArrayDeque();
			que.add(s);
			while (!que.isEmpty()) {
				int cur = que.pollFirst();
				for (int dst = 0; dst < N; ++dst) {
					if (res(cur, dst, flow, cap) <= 0) {
						continue;
					}
					if (dst == s || pre[dst] != -1)
						continue;
					pre[dst] = cur;
					que.addLast(dst);
				}
			}
			if (pre[t] == -1) {
				break;
			}
			int inc = Integer.MAX_VALUE / 3;
			for (int i = t; pre[i] != -1; i = pre[i]) {
				inc = Math.min(inc, res(pre[i], i, flow, cap));
			}
			for (int i = t; pre[i] != -1; i = pre[i]) {
				flow[pre[i]][i] += inc;
				flow[i][pre[i]] -= inc;
			}
			tot += inc;
		}
		return tot;
	}

	void run() {
		Scanner sc = new Scanner();
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int[] a = new int[N];
		int[] b = new int[N];
		int[] c = new int[N];
		int ans = 0;
		boolean[] used = new boolean[N];
		for (int i = 0; i < N; ++i) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
			c[i] = a[i] - b[i];
			if (Math.abs(c[i]) <= A || (B <= Math.abs(c[i]) && Math.abs(c[i]) <= 2 * A)) {
				++ans;
				used[i] = true;
			}
		}
		int[][] cap = new int[N + 2][N + 2];
		for (int i = 0; i < N; ++i) {
			for (int j = i + 1; j < N; ++j) {
				if (used[i] || used[j])
					continue;
				if (Math.abs(c[i] + c[j]) <= A || (B <= Math.abs(c[i] + c[j]) && Math.abs(c[i] + c[j]) <= 2 * A)) {
					cap[i][j] = 1;
					cap[j][i] = 1;
				}
			}
		}
		for (int i = 0; i < N; ++i) {
			if (used[i])
				continue;
			if (c[i] > 0) {
				cap[N][i] = 1;
			} else {
				cap[i][N + 1] = 1;
			}
		}
		ans += solve(N + 2, cap, N, N + 1);
		System.out.println(ans);
	}

	//src->dstにあとどれだけ流せるか。
	int res(int src, int dst, int[][] flow, int[][] cap) {
		return cap[src][dst] - flow[src][dst];
	}

	class Scanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		public int nextInt() {
			long nl = nextLong();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
				throw new NumberFormatException();
			return (int) nl;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}


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
