맨해튼의 아침

시간 제한2초메모리 제한512 MB

요약

맨해튼 격자에서 집에서 회사까지 최단 경로를 따라 이동할 때 지나갈 수 있는 심부름 지점의 최대 개수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

뉴욕에 사는 당신은 늘 바쁘다. 근무 시간이 긴 데다, 하루에 처리해야 하는 볼일 목록도 길다. 아침 일찍 일어나는 것을 싫어해서 볼일은 언제나 퇴근 후에 몰아서 처리하는데, 그러다 보니 여가 시간이 점점 줄어든다.

어느 날 볼일을 봐야 하는 장소 몇 곳이 출근길 위에 있다는 사실을 알아차렸다. 그런 곳은 출근 전에 들를 수 있다. 다음 날에는 경로를 조금만 바꾸면 거리를 전혀 늘리지 않고도 볼일 대부분을 처리할 수 있다는 것을 알게 되었다. 볼일 자체에 걸리는 시간은 무시할 수 있으므로 더 일찍 일어날 필요도 없다. 격자 모양인 뉴욕 도로가 주는 이 효과를 보고 궁금해졌다. 볼일 장소가 모두 주어질 때, 더 일찍 일어나지 않고 출근길에 처리할 수 있는 볼일은 최대 몇 개인가?

뉴욕의 도로망은 $x$ 축과 평행한 거리(street)와 $y$ 축과 평행한 대로(avenue)로 이루어진다. 모든 정수 $a$ 에 대해 $y = a$ 인 거리가 있고, 모든 정수 $b$ 에 대해 $x = b$ 인 대로가 있다. 볼일은 항상 거리와 대로의 교차점에서 일어난다. 걸어서 출근하므로 모든 도로를 양방향으로 이용할 수 있다.

입력

첫째 줄에 그날 처리해야 하는 볼일의 개수 $n$ 이 주어진다. ( $0 \le n \le 10^5$ )
둘째 줄에 집과 직장의 좌표를 나타내는 네 정수 $x_h$ , $y_h$ , $x_w$ , $y_w$ 가 주어진다. ( $0 \le x_h, y_h, x_w, y_w \le 10^9$ )
다음 $n$ 개 줄에 $i$ 번째 볼일의 좌표를 나타내는 두 정수 $x_i$ , $y_i$ 가 주어진다. ( $0 \le x_i, y_i \le 10^9$ )

한 교차점에서 볼일이 여러 개 있을 수 있고, 그 볼일은 각각 따로 센다.

출력

집에서 직장까지 가는 최단 경로보다 길지 않은 경로로 출근하면서 처리할 수 있는 볼일의 최대 개수를 한 줄에 출력한다.

예제3

예제 1
입력
```
3
0 0 6 6
5 4
2 6
3 1
```
예상 출력
```
2
```
예제 2
입력
```
5
2 1 0 0
0 0
0 1
2 0
2 1
3 1
```
예상 출력
```
3
```

예제 3

입력

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

예상 출력