作为一名邪恶科学家，你已经研究出了如何在秘密实验室中制造更大、更可怕的果冻。在你的圆形实验台上，排列着一个包含 $N$ 个矩形果冻的循环数组，每个果冻都有特定的高度和宽度。请注意，第一个果冻和最后一个果冻是相邻的。

你可以将两个相邻的父果冻融合在一起，产生一个高度等于两个父果冻高度的最大值、宽度等于两个父果冻宽度最大值的组合果冻。融合后的果冻会取代它们在循环数组中的位置（此时数组长度减一），并且原则上可以再次与它的两个邻居之一进行融合。

你希望通过执行任意次数的融合操作，使所有果冻的面积之和最大化。毕竟，你的果冻覆盖的总面积越大，你能征服的城市就越多！

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 3 \cdot 10^5$)，表示实验台上最初的果冻数量。

接下来的 $N$ 行按顺序描述这些果冻。第 $i$ 行包含两个空格分隔的整数 $h_i$ 和 $w_i$ ($1 \le h_i, w_i \le 10^6$)，分别表示第 $i$ 个果冻的高度和宽度。

输出格式

输出一个整数：在执行任意次数的融合操作以最优地最大化面积之和后，循环数组中剩余果冻的面积之和。

样例

输入 1

2
6 3
2 7

输出 1

42

输入 2

4
1 5
10 10
5 1
6 7

输出 2

152

输入 3

5
6 2
5 1
1 5
2 7
1 2

输出 3

67

输入 4

1
380385 222650

输出 4

84692720250