개의 행과 개의 열로 이루어진 격자가 있다.
격자 위에 개의 직사각형 영역이 주어진다. 번째 직사각형은 네 정수 로 표현되며, 행 번호가 이상 이하이고 열 번호가 이상 이하인 모든 칸을 덮는다.
주어진 직사각형 중 일부를 선택하려고 한다. 선택한 어떠한 두 직사각형도 같은 격자 칸을 덮어서는 안 된다.
조건을 만족하도록 선택할 수 있는 직사각형의 최대 개수를 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 조건을 만족하도록 선택할 수 있는 직사각형의 최대 개수를 한 줄에 출력한다.
번 직사각형을 선택하면 서로 같은 칸을 덮지 않아 네 개를 선택할 수 있습니다. 번과 번 직사각형은 번 칸을 함께 덮으므로 다섯 개를 모두 선택할 수는 없습니다.
각 케이스는 다음과 같은 형식으로 주어진다.
| 3 | 74 | 추가적인 제약이 없다. |
