과수원
시간 제한2초메모리 제한64 MB
겹치지 않는 최대 2500개의 색칠된 직사각형 과수원이 주어질 때, 한 가지 과일로만 완전히 채워지는 최대 넓이의 축 정렬 직사각형을 구합니다.
문제
직사각형 모양의 과수원들이 넓은 벌판에 놓여 있다. 서로 다른 과수원은 겹치지 않지만, 변을 맞대고 있을 수는 있다. 각 과수원에는 한 종류의 과일만 심어져 있으며, 여러 과수원에 같은 종류의 과일이 심어져 있을 수도 있다.
아래 그림은 두 벌판을 위에서 내려다본 예이다. 같은 색으로 그려진 직사각형은 같은 종류의 과일이 심어진 과수원을 뜻한다.
한 종류의 과일만으로 완전히 채울 수 있는 축에 평행한 직사각형 중 넓이가 가장 큰 것을 찾아 그 넓이를 출력하시오.
입력
첫째 줄에 과수원의 개수 N(1 <= N <= 2,500)이 주어진다.
다음 N개 줄에는 다섯 정수 X1, Y1, X2, Y2, C가 공백으로 구분되어 주어진다. 여기서 X1 < X2, Y1 < Y2이며, 해당 과수원은 (X1, Y1)과 (X2, Y2)를 서로 마주 보는 두 꼭짓점으로 하는 직사각형이다.
좌표는 모두 0 이상 1,000,000,000 이하의 정수이다. C는 그 과수원에 심어진 과일의 종류를 나타내는 번호이다(1 <= C <= 100).
출력
한 종류의 과일만으로 완전히 채워지는 축에 평행한 직사각형의 최대 넓이를 출력한다.