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

Chúa là bậc Thánh nhân vĩ đại! Để tỏ lòng tôn kính với Người, dân chúng ở Bethlehem quyết định xây dựng một khu tưởng niệm thật hoành tráng gọi là "Mảnh đất của Chúa". Tương truyền rằng trước khi bị ghim mình trên thánh giá, Chúa đã để lại bản đồ N khu đất (đất Chúa) mà mình thường hay lui tới, mỗi khu đất có dạng là một hình chữ nhật có các cạnh nằm song song với trục tọa độ, được mô tả bởi tọa độ của một cặp đỉnh đối nhau X_i1, Y_i1, X_i2, Y_i2 (hai khu đất bất kì không giao nhau nhưng có thể có chung cạnh hoặc đỉnh); trên mỗi khu đất ấy được Người trồng một loại cỏ được đánh số là C_i. Dân chúng muốn xây dựng Mảnh đất của Chúa cũng là một hình chữ nhật có cạnh song song với trục tọa độ, nằm hoàn toàn trên lãnh thổ của Chúa (nơi có đất Chúa), trồng cùng một loại cỏ và diện tích lớn nhất có thể được! Hãy giúp người dân Bethlehem tìm được Mảnh đất nói trên trước Giáng sinh này!

Dữ liệu

- Dòng thứ nhất chứa số N.
- N dòng sau, mỗi dòng chứa 5 số nguyên X_i1, Y_i1, X_i2, Y_i2 và C_i tương ứng với dữ liệu về khu đất thứ i của Chúa.

Kết quả

- Gồm một số duy nhất là diện tích lớn nhất tìm được.

Ví dụ

Dữ liệu:
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

Kết quả:
8

Dữ liệu:
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

Kết quả:
9

Giới hạn

- N ≤ 2500.
- 0 ≤ X_i1, Y_i1, X_i2, Y_i2 ≤ 10⁹.
- 1 ≤ C_i ≤ 100.