Problemas
벅스 통합 주식회사는 유명한 고수준 메모리 칩 제조회사이다.
드디어 벅스 통합 주식회사에서 6테라바이트의 Q-RAM 칩을 생산하는데 착수했다.
6개의 정사각형 유닛으로 이루어진 각각의 Q-RAM 칩들은 2*3 직사각형 모양이다.
이와 같은 Q-RAM 칩들은, N*M개의 실리콘 직사각형 판으로 나눠진 정사각형 유닛으로 제작 된다.
조심스럽게 각각의 유닛들을 테스트한 다음, 불량품들은 검은색으로 칠한다.
마지막으로, 이 실리콘 판을 메모리칩들로 자른다. 각각의 칩들은 2*3(혹은 3*2)의 정사각형 모양의 유닛으로 구성된다.
물론 칩들은 불량으로 표시된 사각형은 포함하지 않는다.
이것은 모든 정상 유닛이 메모리칩의 일부가 되어야 하지는 않는다는 것을 의미한다.
이 회사는 가능한 한 정상 유닛들을 조금만 버리고자 한다.
즉, 그들이 원하는 것은 판을 잘라서 가능한 가장 많은 수의 칩을 만드는 방법을 알아보자.
당신에게는 몇몇 실리콘 판들의 치수가 주어지고, 각 판마다 불량 유닛들의 리스트가 주어집니다.
당신은 판을 잘라서 만들 수 있는 칩의 최대 개수들을 각각의 판에 대해서 계산해내는 프로그램들 작성해야 합니다.
Entrada
입력 파일의 첫째 줄은 D (1≤D≤5)라는 정수 하나로 이루어져 있다. 이는 실리콘 판의 수를 의미한다. 하나의 실리콘 판을 설명하는 D개의 블록의 정보가 입력된다. 각 블록의 첫 줄은 세 개의 정수 N, M, K (1≤N≤150, 1≤M≤10, 0≤K≤M, N)가 하나의 공백으로 구분되어 있다. N은 판의 길이를, M은 판의 높이를 나타내며, K는 판때기 안의 불량 유닛의 개수를 의미한다. 그 다음 줄부터 불량 사각형들의 리스트가 K줄에 걸쳐 주어진다. 각각의 줄은 한 불량 유닛의 좌표를 나타내는 두개의 정수 x와 y (1≤x≤N, 1≤y≤M) 로 이루어져 있다. 맨 왼쪽 위 사각형의 좌표는 [1, 1]이며, 맨 오른쪽 아래 사각형의 좌표는 [N, M]이다.
Salida
입력 파일에 주어진 각각의 판에 대해, 판을 잘라서 만들 수 있는 최대 메모리칩의 개수를 한 줄씩 출력하라.
Ejemplo
2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4
3
4
Debes iniciar sesión para escribir código.