각주

책의 본문은 여러 줄로 이루어져 있다. 본문 줄에는 각주 참조가 있을 수 있다. 각주는 하나 이상의 줄로 이루어지며, 각주를 참조한 본문 줄과 같은 페이지에 인쇄되어야 한다.

한 페이지에서 각주를 인쇄하기 시작하면 그 뒤에는 다른 각주만 올 수 있고, 본문 줄은 더 올 수 없다. 따라서 한 페이지에는 연속한 본문 줄 몇 개와 그 본문 줄들이 참조하는 각주들이 함께 들어간다.

한 페이지에 인쇄할 수 있는 최대 줄 수 K가 주어진다. 본문과 각주를 모두 포함하여 어떤 페이지도 K줄을 넘을 수 없다.

책을 인쇄하는 데 필요한 최소 페이지 수를 구하라.

첫째 줄에 본문 줄 수 N과 한 페이지에 인쇄할 수 있는 최대 줄 수 K가 공백으로 구분되어 주어진다. (2 <= N <= 1000, 2 <= K <= 1000)

둘째 줄에 각주의 수 F가 주어진다. (1 <= F <= 100)

다음 F개의 줄에는 두 정수 X와 Y가 공백으로 구분되어 주어진다. 이는 본문의 X번째 줄이 Y줄짜리 각주를 참조한다는 뜻이다. 같은 본문 줄에 여러 각주가 있을 수 있으며, 각주 정보는 참조하는 본문 줄 번호의 오름차순으로 주어진다.

항상 책을 인쇄할 수 있는 입력만 주어진다.

책을 인쇄하는 데 필요한 최소 페이지 수를 출력한다.