题目描述

Donghyun 生活在二维平面上，以 $x$ 轴为地面。二维平面经常下雨，雨水从 $y = \infty$ 处落下。

最近，Donghyun 读了一本名为《水知道答案》的书，并深受启发。他现在相信，只要身边有水，他就会变得超级聪明和机智。

:::align{center}

《水知道答案》一书 :::

Donghyun 有 $N$ 个矩形盒子，它们的高度和宽度（可能）各不相同。他打算重新排列这些盒子以收集雨水。然后，水就会给他答案。为了实现这一点，他必须将盒子排成一行。地面会吸收雨水，因此盒子之间不允许有空隙。他可以旋转某些盒子，也可以不旋转，但必须使盒子的边与地面平行。

水可以向左或向右流动，直到有空间可以流动为止。正式地说，某一点的水可以停留在该位置，当且仅当该点不在盒子内部，并且在其左侧和右侧的同一高度上都有盒子存在。

Donghyun 想知道他能储存的最大水量面积。（在二维平面中，面积即体积。）但是，他现在还没有水，所以他不知道答案。你知道答案吗？

输入格式

第一行包含一个整数 $N$，表示盒子的数量。 ($3 \le N \le 250000$)

接下来的 $N$ 行中，第 $i$ 行包含两个整数 $w_i$ 和 $h_i$，分别表示第 $i$ 个盒子的宽度和高度。 ($1 \le w_i, h_i \le 10^6$)

输出格式

输出一个整数，表示在最优排列盒子时所能储存的最大水量面积。

3
4 3
2 6
5 1

15

提示

:::align{center}

示例输入的最佳排列方式。 :::

翻译由 DeepSeek 完成