Giải bài trực tuyến

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: X_i1, Y_i1, X_i2, Y_i2 (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 C_i. 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 X_i1, Y_i1, X_i2, Y_i2 and C_i describing the i^th 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 ≤ X_i1, Y_i1, X_i2, Y_i2 ≤ 10⁹.
- 1 ≤ C_i ≤ 100.

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