보석 레이스

옆 방향 속도가 제한된 채로 아래에서 위로 달리면서 주울 수 있는 보석의 최대 개수를 구합니다.

보통7동적 계획법정렬이분 탐색아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

레이싱 게임을 한다. 캐릭터는 xx축(y=0y = 0) 위에서 출발해 트랙을 따라 위로 달린다. 트랙의 좌우 경계는 직선 x=0x = 0과 직선 x=wx = w이다. 출발 지점의 가로 좌표는 트랙 안이기만 하면 원하는 대로 고를 수 있다. 결승선은 y=hy = h이고, 이 선에 닿으면 게임이 끝난다.

세로 속도는 vv로 고정되어 있다. 반면 가로 속도는 v/r-v/r 이상 v/rv/r 이하의 값 중 아무 값이나 고를 수 있고, 언제든지 바꿀 수 있다.

트랙 위 정해진 nn개의 지점에 보석이 하나씩 놓여 있다. 보석을 최대한 많이 모으려고 한다. 한 번의 주행에서 모을 수 있는 보석은 최대 몇 개인가?

입력

첫째 줄에 네 정수 nn, rr, ww, hh가 공백으로 구분되어 주어진다 (1n1051 \le n \le 10^5, 1r101 \le r \le 10, 1w,h1091 \le w, h \le 10^9).

다음 nn개의 줄에는 각각 두 정수 xix_iyiy_i가 공백으로 구분되어 주어진다. 이는 ii번째 보석의 좌표이다 (0xiw0 \le x_i \le w, 0<yih0 < y_i \le h). 한 위치에 보석이 둘 이상 놓이는 경우는 없다.

vv의 값은 입력에 주어지지 않는다.

출력

주행 중 모을 수 있는 보석의 최대 개수를 한 줄에 출력한다.