Problem Description

In a 3D histogram, there are $n$ blocks placed. Each of these blocks has a width of 1, and they are arranged such that when viewed from the front, they form a 2D histogram with heights $a_i$ from left to right, and when viewed from above, they form another 2D histogram with heights $b_i$ from left to right.

Determine the maximum volume of a rectangular parallelepiped that can be placed within the histogram, with all its edges parallel to the length, width, and height of the 3D blocks.

Input Format

The first line contains an integer $n$, representing the number of 3D blocks.
The next $n$ lines each contain two integers $a_i$ and $b_i$, as described in the problem.

Output Format

Output a single integer representing the maximum volume of the rectangular parallelepiped that can be placed.

Sample Input and Output

Sample Input #1

5
5 3
4 4
2 1
3 2
1 5

Sample Output #1

24

Sample Input #2

6
3 1
2 1
2 2
2 3
1 1
2 2

Sample Output #2

8

Sample Input #3

5
15 19
5 6
1 13
3 7
1 2

Sample Output #3

285

Notes

Sample 1 Explanation

The described histogram is illustrated in the following image:

The maximum volume of the rectangular parallelepiped that can be placed is $2 \times 4 \times 3 = 24$.

Data Size and Constraints

This problem uses batched testing.

• Subtask 1 (20 points): $1 \le n \le 2000$.
• Subtask 2 (90 points): $1 \le n \le 2 \times 10^5$.

For 100% of the data, $1 \le a_i, b_i \le 10^6$.

This problem is worth a total of 110 points.

Notes

Translated from Croatian Open Competition in Informatics 2020 ~ 2021 Round 1 C 3D Histogram.

见题面 Input 部分

见题面 Output 部分