캡틴 라트비아

시간 제한1초메모리 제한1024 MB

요약

세로로 긴 복도에서 (X,0)에 선 영웅이 왼쪽 벽과 오른쪽 벽의 한 점씩을 향해 방패를 던질 때, 삼각형의 경계에 놓이는 적의 최대 수를 구한다.

난이도: 보통10점 중 7점
유형: 기하, 그리디, 정렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

평면 위에 그려진 무한히 긴 복도를 생각합니다. 복도의 바닥(아래 벽)은 점 $(0, 0)$ 에서 점 $(L, 0)$ 까지 이어지는 선분입니다. 두 옆 벽은 각각 $(0, 0)$ 과 $(L, 0)$ 에서 시작해 위쪽( $y$ 가 커지는 방향)으로 뻗어 나가는 반직선입니다. 즉, 복도는 $0 \le x \le L$ 이고 $y \ge 0$ 인 모든 점의 집합입니다.

복도 안에는 적이 $N$ 명 있습니다. $i$ 번째 적은 점 $(x_i, y_i)$ 에 서 있으며, $0 < x_i < L$ 이고 $y_i > 0$ 입니다.

주인공은 바닥 위의 점 $(X, 0)$ 에 서 있고( $0 < X < L$ ), 제자리에서 방패를 던집니다. 방패는 한쪽 옆 벽 위의 한 점까지 직선으로 날아가고, 거기서 반대쪽 옆 벽 위의 한 점으로 튕겨 나간 뒤, 다시 직선으로 주인공에게 돌아옵니다. 따라서 방패의 궤적은 주인공의 위치 $(X, 0)$ , 왼쪽 벽 위의 한 점, 오른쪽 벽 위의 한 점을 세 꼭짓점으로 하는 삼각형입니다. 이 삼각형의 경계(세 변 중 하나) 위에 있는 모든 적이 쓰러집니다.

주인공은 원하는 대로 조준할 수 있습니다. 즉, 두 벽 위의 꼭짓점을 각 벽의 높이 $0$ 이상인 임의의 위치에 둘 수 있습니다. 한 번 던져서 쓰러뜨릴 수 있는 적의 최대 수를 구하세요.

입력

첫째 줄에 두 정수 $L$ 과 $N$ 이 주어집니다. 각각 바닥의 길이와 적의 수입니다. 둘째 줄에 정수 $X$ 가 주어집니다. 주인공의 $x$ 좌표입니다. 다음 $N$ 개의 줄에는 각각 두 정수 $x_i$ 와 $y_i$ 가 공백으로 구분되어 주어집니다. $i$ 번째 적의 좌표입니다.

출력

한 번 던져서 쓰러뜨릴 수 있는 적의 최대 수를 정수 하나로 출력합니다.

제한

$1 \le N \le 10^5$
$2 \le L \le 10^5$
$0 < X < L$
$0 < x_i < L$
$0 < y_i \le 10^5$
모든 좌표는 정수입니다.

예제3

예제 1
입력
```
5 5
2
1 1
1 4
4 2
3 3
2 6
```
예상 출력
```
3
```
예제 2
입력
```
10 1
5
5 7
```
예상 출력
```
1
```
예제 3
입력
```
10 2
5
2 3
8 3
```
예상 출력
```
2
```