거실의 왕도마뱀

TV 좌표와 N마리 도마뱀의 위치 및 키가 주어질 때, 각 도마뱀이 TV까지의 선분 위에 있는 모든 도마뱀보다 키가 크도록 남길 수 있는 최대 마릿수를 구한다.

보통7기하정렬그리디구현아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

왕도마뱀은 냉혈성과 컴퓨터 화면 중독으로 유명한 파충류다. 영어 이름이 monitor lizard인 만큼 화면을 좋아해서, 하루 대부분을 거실의 작은 텔레비전 앞에 붙어서 보낸다.

한 파충류관에서 문제가 생겼다. 모여든 도마뱀이 너무 많아 이제는 모두가 화면을 볼 수 없다. 도마뱀은 자기 자리에서 텔레비전까지 이은 선분 위에 앉은 모든 도마뱀보다 키가 엄격하게 클 때만 화면을 본다.

도마뱀은 화면에 무엇이 나오는지, 비스듬히 보는지 정면으로 보는지 따지지 않는다. 화면이 시야에 들어오기만 하면 된다.

대신 자리는 옮기지 않는다. 뒤에 앉은 도마뱀이 보도록 어떤 도마뱀을 방 밖으로 내보내거나 그대로 둘 수 있지만, 방 안의 다른 자리로 옮기는 것은 불가능하다.

도마뱀을 최적으로 내보낼 때, 최대 몇 마리가 남아서 화면을 볼 수 있는가?

입력

  • 첫째 줄에 텔레비전의 좌표를 나타내는 정수 TXTXTYTY가 공백으로 구분되어 주어진다 (106TX,TY106-10^6 \le TX, TY \le 10^6).
  • 둘째 줄에 도마뱀의 수를 나타내는 정수 NN이 주어진다 (1N1061 \le N \le 10^6).
  • 다음 NN개 줄에 도마뱀 한 마리의 좌표와 키를 나타내는 정수 XiX_i, YiY_i, HiH_i가 공백으로 구분되어 주어진다 (106Xi,Yi106-10^6 \le X_i, Y_i \le 10^6, 1Hi1061 \le H_i \le 10^6).

텔레비전과 도마뱀 NN마리의 좌표는 모두 서로 다르다.

출력

화면을 동시에 볼 수 있는 도마뱀 수의 최댓값을 출력한다.