题目描述

译自 COCI 2020/2021 Contest #1 T3「3D Histogram」

Malnar 先生（通过电话）：听着，我曾在大半夜在 Zagreb 周边贴过一些海报。我遇见了一排栅栏，用不同高度的木板拼成的栅栏，我正想着如何计算我能在这排栅栏上贴上的最大的海报面积。你觉得那会是一道不错的 COCI 题吗？

同事：你在干啥啊？！而且吧，这题也不怎么好。不过是一个用单调队列的套路题罢了，我们甚至在我们的 x 令营里教小学生这些东西呢。

Malnar 先生：如果你稍微改编一下，比如对每个前缀都求一遍之类的，那应该够难了吧。

同事：那就和去年我们的 CERC 资格赛撞题了（H 题）。那题挺难的，难点在 Harbingers 一题（CEOI 2009）采用的技巧上（指在凸包上二分更新 DP），但是现在大家都见过了。

Malnar 先生：你确定我们真的束手无策了吗？

同事：我觉得我们已经出完了所有直方图类型的题目了。COCI 2010/2011 的 Tabovi，COCI 2015/2016 的 Poplava，COCI 2017/2018 的 Krov，2018 年的 IOI 选拔赛的 Histogram…… 你懂的。

Malnar 先生：如果直方图是三维的呢？

同事：嗯……

给定一张三维的直方图，包含 $n$ 个接连排列的块。第 $i$ 个块有 $1$ 米宽，$a_i$ 米高，$b_i$ 米长。换句话说，从前面看，就像是每组高度分别为 $a_1, a_2, \ldots , a_n$ 的直方图，从上面看，就像是每组高度分别为 $b_1, b_2, \ldots , b_n$ 的直方图。

请求出三维直方图中能放下的最大体积的长方体。长方体的各个面需要和组成三维直方图的所有块的各个面平行。

输入格式

第一行一个正整数 $n$。
接下来 $n$ 行，第 $i$ 行两个正整数 $a_i, b_i$。

输出格式

输出最大的体积的立方米数。

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

数据范围与提示

译者：PinkRabbit