시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 1115 168 (15%) 145
문제
집과 사무실을 통근하는 $n$명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 $A, B$에 대하여, $A$의 집 혹은 사무실의 위치가 $B$의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 $d$로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다. 양의 정수 $d$와 $n$개의 정수쌍, $(h_{i},o_{i}), 1 \le i \le n$,이 주어져 있다. 여기서 $h_{i}$와 $o_{i}$는 사람 $i$의 집과 사무실의 위치이다. 길이 $d$의 모든 선분$L$에 대하여, 집과 사무실의 위치가 모두 $L$에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오. ![image1](/download_file/66e62334908f45072bee2a472d88d96b8b42c285cddc9b917d195518e0e5dea7/image.png/?show=true) 위의 그림에 있는 예를 고려해보자. 여기서 $n=8$, $(h_{1},o_{1})=(5,40)$,$(h_{2},o_{2})=(35,25)$, $(h_{3},o_{3})=(10,20)$, $(h_{4},o_{4})=(10,25)$, $(h_{5},o_{5})=(30,50)$, $(h_{6},o_{6})=(50,60)$, $(h_{7},o_{7})=(30,25)$, $(h_{8},o_{8})=(80,100)$이고, $d = 30$이다. 이 예에서, 위치 $10$과 $40$사이의 빨간색 선분 $L$이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 $4$이다.
입력
첫 번째 줄에 사람 수를 나타내는 양의 정수 $n (1 \le n \le 100,000)$이 주어진다. 다음 $n$개의 각 줄에 정수 쌍 $(h_{i}, o_{i})$가 주어진다. 여기서 $h_{i}$와 $o_{i}$는 $-100,000,000$이상, $100,000,000$이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 $d(1 \le d \le 200,000,000)$가 주어진다.
출력
길이 $d$의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다.
힌트
#### 입력 예제 1 ``` 8 5 40 35 25 10 20 10 25 30 50 50 60 30 25 80 100 30 ``` #### 출력 예제 1 ``` 4 ``` #### 입력 예제 2 ``` 4 20 80 70 30 35 65 40 60 10 ``` #### 출력 예제 2 ``` 0 ``` #### 입력 예제 3 ``` 5 -5 5 30 40 -5 5 50 40 5 -5 10 ``` #### 출력 예제 3 ``` 3 ```