HCN3D - The God-land

no tags 

How great is our God! To show the respect for God, Bethlehem people decide to build a large area for memorial called "The God-land". There's a story that God used to visit N areas which is rectangles having edges paralell to the axises, described by the co-ordinate of a pair of opposite vertices: Xi1, Yi1, Xi2, Yi2 (any two of them may have no common point, one common vertex or one common edge at most); on which of them there is a kind of grass called Ci. People there want to build the God-land which is also a rectangle having edges parallel to the axises, putting on area(s) mentioned above, having a same kind of grass and having the maximum area! Help them to find the God-land before this Christmas!

Input

- The first line contains N.
- Next N line(s), each line contains Xi1, Yi1, Xi2, Yi2 and Ci describing the ith area to which God used to visit.

Output

- The maximum area found.

Sample

Input:
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

Output:
8

Input:
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

Output:
9

Limitations

- N ≤ 2500.
- 0 ≤ Xi1, Yi1, Xi2, Yi2 ≤ 109.
- 1 ≤ Ci ≤ 100.

Sorry for my bad English!^_^ Please comment for a better translation ;)


hide comments
AnhDQ: 2009-05-24 00:53:04

sorry, im a newbie so i dont know the differences much:d

Robert Gerbicz: 2009-05-24 00:53:04

Moved it back to classical. Why would it be a challenge?

AnhDQ: 2009-05-24 00:53:04

Input has no 0-area rectangle! and if you ask why your submit results 0, its WA all test cases ;)

Last edit: 2009-05-07 15:47:12
ufuk altunbulak: 2009-05-24 00:53:04

What does it mean result=0

AnhDQ: 2009-05-24 00:53:04

Updated Time limit! enjoy!

[Trichromatic] XilinX: 2009-05-24 00:53:04

Time limit too strict.


Added by:AnhDQ
Date:2009-05-02
Time limit:0.200s-0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:AnhDQ (re-coverd)