놀이동산 롤러코스터

놀이동산의 롤러코스터는 키 H cm 이상인 사람만 탑승할 수 있다. N명이 그룹을 이루어 줄을 서 있으며, 같은 그룹은 반드시 함께 탑승해야 한다. 롤러코스터는 한 번에 최대 M명이 탑승할 수 있다.

그룹 중 한 명이라도 키가 H cm 미만이면 해당 그룹은 탑승할 수 없다. 탑승 가능한 그룹들을 순서대로 최대한 태워 운행 횟수를 최소화하여라.

입력

첫째 줄에 키 제한 H, 최대 탑승 인원 M, 사람 수 N이 주어진다. 다음 N줄에 걸쳐 각 사람의 키와 그룹 번호가 주어진다. 줄 서 있는 순서대로 주어진다.

출력

최소 운행 횟수를 출력한다. 탑승 가능한 그룹이 없으면 0을 출력한다.

제한

• 1 ≤ H ≤ 300
• 1 ≤ M ≤ 100
• 1 ≤ N ≤ 1000
• 1 ≤ 그룹 번호 ≤ 100
• 같은 그룹의 사람들은 연속해서 줄을 선다

예제 입력 1

150 4 10
160 1
170 1
155 1
140 2
180 2
165 3
162 3
158 4
155 4
160 4

예제 출력 1

3

예제 입력 2

160 6 10
160 1
170 1
155 1
140 2
180 2
165 3
162 3
158 4
155 4
160 4

예제 출력 2

1

설명: 예제 1에서 그룹2(140cm 포함)와 그룹4(158cm 포함)는 탑승 불가. 그룹1(3명)과 그룹3(2명)이 탑승 가능하다. M=4이므로 그룹1은 단독 1회, 그룹3은 1회로 총 2회. 그룹4도 탑승 가능하므로 3회.