Manhattan Mornings

Time limit2sMemory limit512 MB

Summary

Choose a monotone shortest path from house to workplace on the Manhattan grid that passes through as many errand points as possible.

Level: Medium7 of 10
Topics: Dynamic programming, Sorting, Array
Solved: No attempts yet

Problem

As a New Yorker you are always busy. Your workday is long, and on top of that you keep a long list of errands to run on any given day. You hate getting up early, so you always work through the list after the office, and that is eating into your free time.

One day you notice that some of the places you have to visit lie on your walk to the office, so you can stop there before work. The next day you notice that a slightly different route lets you run most of your errands without making the walk any longer. An errand takes a negligible amount of time, so you do not have to get up any earlier. This effect of the grid-like New York streets gets you thinking. Given the locations of all your errands on the New York grid, how many of them can you visit on the way to work without getting up any earlier?

The New York grid is modelled with streets parallel to the $x$ -axis and avenues parallel to the $y$ -axis. There is a street $y = a$ for every integer $a$ , and there is an avenue $x = b$ for every integer $b$ . An errand always takes place at an intersection of a street and an avenue. You walk to work, so you can use every road in both directions.

Input

The first line contains an integer $n$ , the number of errands you have to run that day ( $0 \le n \le 10^5$ ).
The second line contains four integers $x_h$ , $y_h$ , $x_w$ , $y_w$ , the coordinates of your house and of your workplace ( $0 \le x_h, y_h, x_w, y_w \le 10^9$ ).
Each of the next $n$ lines contains two integers $x_i$ and $y_i$ , the coordinates of your $i$ -th errand ( $0 \le x_i, y_i \le 10^9$ ).

Several errands can take place at one intersection, and each of them is counted separately.

Output

Print one line with the largest number of errands you can run before work on a route that is no longer than the shortest walk from your house to your workplace.

Examples3

Example 1
Input
```
3
0 0 6 6
5 4
2 6
3 1
```
Expected output
```
2
```
Example 2
Input
```
5
2 1 0 0
0 0
0 1
2 0
2 1
3 1
```
Expected output
```
3
```

Example 3

Input

4
200 100 100 200
50 150
200 200
100 100
100 100

Expected output