시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 216 72 63 40.385%

문제

데카는 회사의 화장실을 이용하려고 했다. 하지만 수도 시설 고장으로 회사 내의 모든 화장실 사용이 금지됐고, 사원들은 단 하나의 임시 화장실을 이용해야 했다. 

임시 화장실의 앞에 데카를 포함한 N명의 사원이 대기하고 있다. 데카는 N명의 줄에서 + 1번째로 줄을 섰다. 즉, 데카보다 먼저 도착한 사람이 K명이 있다. 줄이 길어지자 사장은 M개의 줄로 나눠서 대기하라 하였다.

N명의 사원은 순서대로 M개의 줄로 나눠 섰다. 기존 줄의 1번째 사원은 1번째 줄에, 2번째 사원은 2번째 줄에, ... M번째 사원은 M번째 줄에, 그리고 + 1번째 사원은 1번째 줄의 뒤에 서는 방식이다. 

M개의 줄로 나눠 선 것을 본 사장은 매우 흡족해하며 자리를 떠났다.

M개의 줄의 사원들은 암묵적으로 다음의 규칙에 따라 화장실을 이용하기로 하였다.

  • 선두란, 어떤 줄에서 가장 먼저 와서, 가장 앞에 선 사람을 말한다.
  • M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 화장실을 이용한다.
  • M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 둘 이상인 경우, 해당 선두들 중 화장실이 급한 정도 Hi가 가장 높은 선두가 화장실을 이용한다.
  • M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 둘 이상이며, 해당 선두들의 화장실이 급한 정도 Hi도 모두 같다면, 해당 선두 중 줄의 번호가 가장 낮은 줄에 선 선두가 화장실을 이용한다.

과연 몇 명의 사원이 화장실을 이용하고 나서야 데카의 차례가 올까? 매우 초조해지기 시작한 데카를 대신해 계산해주자.

입력

첫 번째 줄에는 임시 화장실에 대기하고 있는 사원의 수 N (1 ≤ N ≤ 105), 사장이 지시한 새로운 줄의 수 M (2 ≤ M ≤ 105), 데카가 화장실에 도착했을 때 자신의 앞에 서 있던 사원의 수 K (0 ≤ K ≤ N − 1)가 빈칸을 사이에 두고 주어진다.

두 번째 줄부터 각 N개의 줄에 임시 화장실에 i번째로 줄을 섰던 사원의 근무 일수 Di (0 ≤ Di ≤ 36,500), 화장실이 급한 정도를 나타내는 정수 Hi (0 ≤ Hi ≤ 108)가 가장 먼저 도착한 사원부터 빈칸을 사이에 두고 주어진다.

출력

데카가 화장실을 이용하기까지 몇 명의 사원이 화장실을 이용할 것인지 출력한다.

예제 입력 1

6 3 2
3000 100
1500 200
1000 500
1500 100
1500 100
1500 100

예제 출력 1

4

예제 입력 2

1 2 0
100 100

예제 출력 2

0

예제 입력 3

3 10 2
450 1000
450 500
450 1000

예제 출력 3

1

힌트

위와 같이 줄을 선 경우를 생각해보자. (x, y) 는 사원의 근무 일수가 x, 화장실이 급한 정도가 y임을 나타낸다. [x, y]는 해당 사원이 데카임을 의미한다. 즉, 위의 그림에서 데카는 3번 사원이다.

이 경우 대기 중인 사원의 수 N은 6이다. 데카의 앞에는 두 명이 있으므로 K는 2다. 이때 사장이 3개의 줄로 나눠 설 것을 지시한다면,

와 같이 나눠 설 수 있다. 이때 데카는 줄 번호 3의 선두다.

이제 화장실을 어떤 선두들이 이용하는지 알아보자.

이 경우 근무 일수가 가장 높은 줄 번호 1의 선두가 화장실을 이용한다.

줄 번호 1, 2의 선두가 근무 일수는 1,500으로 같지만, 화장실이 급한 정도는 줄 번호 2의 선두가 더 높기 때문에 줄 번호 2의 선두가 화장실을 이용한다.

줄 번호 1, 2의 선두가 근무 일수도 1,500으로 같고, 화장실이 급한 정도도 100으로 같지만, 줄 번호는 1이 더 낮기 때문에 줄 번호 1의 선두가 화장실을 이용한다.

줄 번호 2의 선두가 근무 일수가 제일 높기 때문에 화장실을 이용한다.

줄 번호 3의 선두가 근무 일수가 제일 높으며, 이 사원이 데카이므로 줄에 서 있던 인원 중 데카보다 먼저 화장실을 이용한 사원의 수 4를 출력하면 정답이다.