시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 4 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)

출력

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

예제 입력 1

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

예제 출력 1

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
W3sicHJvYmxlbV9pZCI6IjE4MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZmNcdWMyMThcdWM2ZDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHVhY2ZjXHVjMjE4XHVjNmQwXHViNGU0XHVjNzc0IFx1YzYzOVx1YWUzMFx1Yzg4NVx1YWUzMCBcdWJhYThcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YjExM1x1Yzc0MCBcdWJjOGNcdWQzMTBcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWNmY1x1YzIxOFx1YzZkMFx1YjRlNFx1Yzc0MCBcdWFjYjlcdWNjZDAgXHVjNzg4XHVjOWMwXHViMjk0IFx1YzU0YVx1YzljMFx1YjljYywgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU2MCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWNmY1x1YzIxOFx1YzZkMFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVjODg1XHViOTU4XHVjNzU4IFx1YWNmY1x1Yzc3Y1x1YjljY1x1Yzc3NCBcdWMyZWNcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJiM2NcdWI4NjAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjZmNcdWMyMThcdWM2ZDBcdWM1ZDAgXHVhYzE5XHVjNzQwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWFjZmNcdWM3N2NcdWM3NzQgXHVjMmVjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM1NDRcdWI3OThcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1ZDBjMFx1YWNlMCBcdWMwYzFcdWFjZjVcdWM1ZDBcdWMxMWMgXHViYzE0XHViNzdjXHViY2Y4IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYzhjXHVkMzEwXHVjNzQ0IFx1YWRmOFx1YjliY1x1YzczY1x1Yjg1YyBcdWIzYzRcdWMyZGRcdWQ2NTRcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjMGM5XHVjNzNjXHViODVjIFx1YWRmOFx1YjgyNFx1YzljNCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhYzE5XHVjNzQwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWFjZmNcdWM3N2NcdWM3NzQgXHVjMmVjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjZmNcdWMyMThcdWM2ZDBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZydWl0LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0NHB4OyBsaW5lLWhlaWdodDoyMC44cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo1NTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWFjMTlcdWM3NDAgXHVjMGM5XHVjNzNjXHViODVjIFx1Y2U2MFx1ZDU3NFx1YzljNCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzgzXHVjNzU4IFx1YjExM1x1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2ZjXHVjMjE4XHVjNmQwXHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEmbGU7TiZsZTsyLDUwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlNFx1YzEyZiBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFgxLCBZMSwgWDIsIFkyLCBDXHVhYzAwIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChYMSZsdDtYMiwgWTEmbHQ7WTIpIFx1Yzc3NFx1YjI5NCBcdWFjZmNcdWMyMThcdWM2ZDBcdWM3NzQgKFgxLCBZMSksIChYMiwgWTIpXHViOTdjIFx1YjQ1MCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3M2NcdWI4NWMgXHVkNTU4XHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjODhjXHVkNDVjXHViMjk0IDAgXHVjNzc0XHVjMGMxIDEsMDAwLDAwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gQ1x1YjI5NCBcdWM3NzQgXHVhY2ZjXHVjMjE4XHVjNmQwXHVjNWQwIFx1YzJlY1x1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVhY2ZjXHVjNzdjXHVjNzU4IFx1Yzg4NVx1Yjk1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYzg4XHVkNjM4XHVjNzc0XHViMmU0LiAoMSZsZTtDJmxlOzEwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMTlcdWM3NDAgXHVjMGM5XHVjNzNjXHViODVjIFx1Y2U2MFx1ZDU3NFx1YzljNCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzgzXHVjNzU4IFx1YjExM1x1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTgzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InBvbGphIiwiZGVzY3JpcHRpb24iOiI8cD5NaWNrZXkgaXMgaW4gdGhlIGFpcnBsYW5lIGFib3ZlIGdyb3VuZC4gT24gdGhlIGdyb3VuZCwgaGUgc2VlcyBmaWVsZHMgb2YgcmVjdGFuZ3VsYXIgc2hhcGVzIGFuZCBkaWZmZXJlbnQgY29sb3JzLCBkZXBlbmRpbmcgb24gcGxhbnRlZCB2ZWdldGF0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaWNrZXkgd2FudHMgdG8ga25vdyB3aGF0IGlzIHRoZSBhcmVhIG9mIHRoZSBsYXJnZXN0IG9uZS1jb2xvcmVkIHJlY3RhbmdsZSBvbiB0aGUgZ3JvdW5kLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbiB0aGUgcGljdHVyZSB5b3UgY2FuIHNlZSBleGFtcGxlcyBmcm9tIHRoZSBib3R0b20gb2YgdGhlIHBhZ2UgKHNvbHV0aW9uIGZvciBlYWNoIGV4YW1wbGUgaXMgbWFya2VkKTombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mcnVpdC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDRweDsgd2lkdGg6NTUwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgdGhlIGFyZWEgb2YgdGhlIGxhcmdlc3Qgb25lLWNvbG9yZWQgcmVjdGFuZ2xlIG9uIHRoZSBncm91bmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlR3byBkaWZmZXJlbnQgZmllbGRzIHdpbGwgbm90IG92ZXJsYXAsIGhvd2V2ZXIgdGhleSBtYXkgdG91Y2ggaW4gY29ybmVycyBvciBhbG9uZyBzaWRlcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOLCAxICZsZTsgTiAmbGU7IDI1MDAsIHRoZSBudW1iZXIgb2YgZmllbGRzIG9uIHRoZSBncm91bmQuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGZpdmUgaW50ZWdlcnMgWDEsIFkxLCBYMiwgWTIgKFgxJmx0O1gyLCBZMSZsdDtZMikgYW5kIEMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXNlIG51bWJlcnMgcmVwcmVzZW50cyBvbmUgZmllbGQgKHdpdGggc2lkZXMgcGFyYWxsZWwgdG8gY29vcmRpbmF0ZSBheGVzKSB3aXRoIGNvb3JkaW5hdGVzIG9mIGRpYWdvbmFsIGNvcm5lcnMgKFgxLFkxKSBhbmQgKFgyLFkyKSBhbmQgd2l0aCBjb2xvciBDLCAxICZsZTsgQyAmbGU7IDEwMC4gQWxsIHRoZSBjb29yZGluYXRlcyB3aWxsIGJlIGludGVnZXJzIGJldHdlZW4gMCBhbmQgMSwwMDAsMDAwLDAwMCAoaW5jbHVzaXZlKS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5GaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgYXJlYSBmcm9tIHRoZSBwcm9ibGVtIHN0YXRlbWVudC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogc29sdXRpb24gd2lsbCBhbHdheXMgZml0IGludG8gdGhlIHNpZ25lZCA2NC1iaXQgaW50ZWdlciBkYXRhIHR5cGUgKGludDY0IGluIFBhc2NhbCwgbG9uZyBsb25nIGluIENcL0MrKykuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d