题目描述

作为一位邪恶科学家，你已经掌握了如何在秘密实验室中制造更大、更恐怖的果冻怪。在你的圆形实验台周围，摆放着一个由 $N$ 个矩形果冻组成的 环形数组，每个果冻都有一定的高度和宽度。注意，第一个果冻和最后一个果冻是相邻的。

你可以将两个相邻的父果冻融合在一起，生成一个新的组合果冻，其高度等于两个父果冻高度的最大值，宽度等于两个父果冻宽度的最大值。融合后的果冻会替换掉原来两个父果冻在环形数组中的位置（此时数组长度减少 1），并且原则上它可以继续与它相邻的两个果冻之一再次融合。

你可以进行任意次数的融合操作，目的是最大化所有果冻的面积之和。毕竟，你的果冻能覆盖的总面积越大，你能征服的城市就越多！

输入格式

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

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

输出格式

输出一个整数：在任意次融合操作后，环形数组中剩余的果冻的面积之和的最大可能值。

输入输出样例 #1

输入 #1

2
6 3
2 7

输出 #1

42

输入输出样例 #2

输入 #2

4
1 5
10 10
5 1
6 7

输出 #2

152

输入输出样例 #3

输入 #3

5
6 2
5 1
1 5
2 7
1 2

输出 #3

67

输入输出样例 #4

输入 #4

1
380385 222650

输出 #4

84692720250