马尔纳先生（电话中）：听着，我半夜得在萨格勒布周围贴一些海报。我偶然发现了一个由不同高度的木板组成的栅栏，我当时就在想，如何计算出能贴在栅栏上的海报的最大面积。这难道不是一个很好的 COCI 题目吗？

助手：你在干什么？！不管怎样，这题不好。这是一个用单调队列的经典套路，我们甚至在夏令营里教小学生这个。

马尔纳先生：如果稍微改动一下呢，比如要求每个前缀的答案，这应该足够难了吧。

助手：去年我们的 CERC 预选赛中就出现了完全相同的题目。那是一道难题，归结为 Harbingers 技巧，但现在大家都见过了。

马尔纳先生：你确定我们无能为力了吗？

助手：我觉得我们已经把所有关于直方图的题目都出光了。COCI 2010/2011 (Tabovi)、COCI 2015/2016 (Poplava)、COCI 2017/2018 (Krov)、IOI 2018 选拔赛 (Histogram)……你懂的。

马尔纳先生：如果直方图是三维的呢？

助手：呃……

给你一个三维直方图，它由 $n$ 个相邻放置的块组成。第 $i$ 个块的宽度为 $1$ 米，高度为 $a_i$ 米，长度为 $b_i$ 米。换句话说，从正面看，它是一个条形高度为 $a_1, a_2, \dots, a_n$ 的直方图；从上方看，它是一个条形高度为 $b_1, b_2, \dots, b_n$ 的直方图。

确定可以放置在给定的三维直方图内部的最大体积的长方体。该长方体的各边需要与组成三维直方图的块的各边平行。

输入格式

第一行包含题目描述中的整数 $n$。

接下来的 $n$ 行中，第 $i$ 行包含题目描述中的整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^6$）。

输出格式

输出以立方米为单位的体积。

子任务

样例

输入样例 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

说明

下图展示了第一个样例中的三维直方图。最大长方体是通过使用前两个块的一部分得到的，它的宽为 $2$ 米，高为 $4$ 米，长为 $3$ 米。该长方体的体积为 $2 \cdot 4 \cdot 3 = 24$ 立方米。