P7164 [COCI 2020/2021 #1] 3D Histogram

~~The background of the original problem is actually a common “trap problem” story. If you are interested, you can go and read it. I am too lazy to translate it here.~~

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.

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 one integer, the maximum volume of a rectangular cuboid that can be placed.

#### 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](https://hsin.hr/coci/archive/2020_2021/contest1_tasks.pdf)。 Translated by ChatGPT 5