Description

In a 3D histogram, we place $n$ 3D blocks. Each block has width $1$. Viewed from the front, they form a 2D histogram whose heights from left to right are $a_i$. Viewed from the top, they form a 2D histogram whose heights from left to right are $b_i$.

Find the volume of the largest rectangular cuboid that can be placed inside the histogram. All edges of the cuboid must be parallel to the width, length, 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, b_i$, as described above.

Output Format

Output one integer, the maximum volume of a rectangular cuboid that can be placed.

5
5 3
4 4
2 1
3 2
1 5

24

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

8

5
15 19
5 6
1 13
3 7
1 2

285

Hint

Explanation for Sample 1

The histogram described is shown in the figure below:

The maximum cuboid volume that can be placed is $2 \times 4 \times 3 = 24$.

Constraints and Notes

This problem uses bundled testdata.

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

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

The full score of this problem is $110$ points.

Note

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

Translated by ChatGPT 5