문제
가로 C칸, 세로 R칸의 초콜릿이 있다. 선생님은 이 초콜릿을 가로 또는 세로 방향으로 N번 자르고 학생들에게 나눠주려고 한다. 잘린 M개의 조각은 왼쪽 위의 것부터 세면서 1~M의 번호를 매긴다.
선생님은 모의고사 점수를 토대로 등수를 나누고, 1등에서부터 M등까지 초콜릿을 나눠주려고 한다. 선생님은 초콜릿 조각들을 크기가 큰 순서대로(만약 크기가 같은 초콜릿이 여러 개라면 번호가 작은 순으로) 1등에서부터 M등까지 차례대로 초콜릿 한 조각을 주게 된다. 예를 들어, 위 그림에서는 1~6등에게 각각 3, 5, 1, 4, 6, 2번 초콜릿을 줄 것이다.
초콜릿을 자르다 보니 조각이 너무 많아서 뭐가 몇 번째로 큰 조각인지 알기가 힘들어졌다. 선생님을 도와 K등에게 몇 번 초콜릿을 줘야 할지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 초콜릿의 크기 R, C와 자르는 횟수 N이 주어진다. 1 ≤ R, C ≤ 108, 1 ≤ N ≤ min(R+C-2, 400,000)
두 번째 줄부터 N개의 줄에는 초콜릿을 자르는 방향 Dk, 초콜릿을 자르는 위치 Pk 가 주어진다. Dk = 0 이면 초콜릿을 가로로 자른다는 말이며 이때 1 ≤ Pk ≤ R-1이다. Dk = 1 이면 초콜릿을 세로로 자른다는 말이며 이때 1 ≤ Pk ≤ C-1이다. 마지막 줄에는 초콜릿을 받는 학생의 등수 K (1 ≤ K ≤ R × C)가 주어진다.
전체 데이터의 1/2는 조각의 수가 1,000,000을 넘지 않는다. 전체 데이터의 1/2는 R, C ≤ 200,000을 만족한다. 전체 데이터의 2/3은 위 조건들 중 적어도 하나 이상을 만족시킨다.
출력
만약 학생이 초콜릿을 받지 못한다면 "No Chocolate"를 출력한다.
그렇지 않으면 학생이 받는 초콜릿의 번호를 출력한다.
예제 #1
5 6 3
0 3
1 4
0 1
3
1
예제 #2
3 3 4
0 1
0 2
1 1
1 2
12
No Chocolate
로그인해야 코드를 작성할 수 있어요.