## 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:51 1 3 3 13 1 5 3 11 4 3 6 13 4 5 6 10 3 6 4 2Output:8`

`Input:55 5 6 6 223 4 6 5 226 3 7 6 225 6 8 7 224 5 5 8 22Output:9`

### Limitations

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

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