거실의 왕도마뱀
시간 제한5초메모리 제한512 MB
TV 좌표와 N마리 도마뱀의 위치 및 키가 주어질 때, 각 도마뱀이 TV까지의 선분 위에 있는 모든 도마뱀보다 키가 크도록 남길 수 있는 최대 마릿수를 구한다.
문제
왕도마뱀은 냉혈성과 컴퓨터 화면 중독으로 유명한 파충류다. 영어 이름이 monitor lizard인 만큼 화면을 좋아해서, 하루 대부분을 거실의 작은 텔레비전 앞에 붙어서 보낸다.
한 파충류관에서 문제가 생겼다. 모여든 도마뱀이 너무 많아 이제는 모두가 화면을 볼 수 없다. 도마뱀은 자기 자리에서 텔레비전까지 이은 선분 위에 앉은 모든 도마뱀보다 키가 엄격하게 클 때만 화면을 본다.
도마뱀은 화면에 무엇이 나오는지, 비스듬히 보는지 정면으로 보는지 따지지 않는다. 화면이 시야에 들어오기만 하면 된다.
대신 자리는 옮기지 않는다. 뒤에 앉은 도마뱀이 보도록 어떤 도마뱀을 방 밖으로 내보내거나 그대로 둘 수 있지만, 방 안의 다른 자리로 옮기는 것은 불가능하다.
도마뱀을 최적으로 내보낼 때, 최대 몇 마리가 남아서 화면을 볼 수 있는가?
입력
- 첫째 줄에 텔레비전의 좌표를 나타내는 정수 와 가 공백으로 구분되어 주어진다 ().
- 둘째 줄에 도마뱀의 수를 나타내는 정수 이 주어진다 ().
- 다음 개 줄에 도마뱀 한 마리의 좌표와 키를 나타내는 정수 , , 가 공백으로 구분되어 주어진다 (, ).
텔레비전과 도마뱀 마리의 좌표는 모두 서로 다르다.
출력
화면을 동시에 볼 수 있는 도마뱀 수의 최댓값을 출력한다.