시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 3 2 2 66.667%

문제

직사각형 모양의 과수원들이 옹기종기 모여 있는 넓은 벌판이 있다. 서로 다른 과수원들은 겹쳐 있지는 않지만, 변을 공유할 있을 수는 있다. 각각의 과수원에는 한 종류의 과일만이 심어져 있다. 물론 서로 다른 과수원에 같은 종류의 과일이 심어져 있을 수도 있다. 아래는 비행기를 타고 상공에서 바라본 두 개의 벌판을 그림으로 도식화한 것이다. 같은 색으로 그려진 직사각형은 같은 종류의 과일이 심어져 있는 과수원이 된다.

같은 색으로 칠해진 직사각형 중에서 가장 큰 것의 넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 과수원의 개수 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)

출력

같은 색으로 칠해진 직사각형 중에서 가장 큰 것의 넓이를 출력한다.

예제 입력

5
1 1 3 3 1
3 1 5 3 1
1 4 3 6 1
3 4 5 6 1
0 3 6 4 2

예제 출력

8

예제 입력 2

5
5 5 6 6 22
3 4 6 5 22
6 3 7 6 22
5 6 8 7 22
4 5 5 8 22

예제 출력 2

9

예제 입력 3

7
0 0 4 3 1
6 2 9 7 2
6 7 10 9 3
4 0 6 3 1
0 6 6 9 3
0 3 6 6 2
7 0 8 2 2

예제 출력 3

27

힌트