[COCI2020-2021#1] 3D Histogram

题目背景

~~原题目背景其实是一个出毒瘤题的套路，有兴趣的同学可以去看看，这里懒得翻译了~~

题目描述

在一个三维直方图中，放入 $n$ 个三维块，这些三维块的宽度均为 $1$，且能使得在正面看是一个从左到右分别高度为 $a_i$ 的二维直方图，在上面看是一个从左到右分别高度为 $b_i$ 的二维直方图。 求在直方图中能放入的最大体积长方体的体积是多少，长方体的所有边均要与三维块的长宽高平行。

输入输出格式

输入格式


第一行一个整数 $n$ 代表三维块数量。 接下来 $n$ 行每行两个整数 $a_i,b_i$，如题目描述。

输出格式


一行一个整数代表能放入的最大长方体体积。

输入输出样例

输入样例 #1

5
5 3
4 4
2 1
3 2
1 5

输出样例 #1

24

输入样例 #2

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

输出样例 #2

8

输入样例 #3

5
15 19
5 6
1 13
3 7
1 2

输出样例 #3

285

说明

#### 样例 1 解释 描述的直方图如下图所示： ![](https://cdn.luogu.com.cn/upload/image_hosting/z2txhsvt.png) 能放入的最大长方体体积为 $2 \times 4 \times 3=24$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（20 pts）：$1 \le n \le 2000$。 - Subtask 2（90 pts）：$1 \le n \le 2 \times 10^5$。 对于 $100\%$ 的数据，$1 \le a_i,b_i \le 10^6$。 **本题满分 $110$ 分。** #### 说明 翻译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 1 C 3D Histogram](https://hsin.hr/coci/contest1_tasks.pdf)。