邪悪な科学者であるあなたは、秘密の研究所でより大きく恐ろしいゼリーを作り出す方法を見つけ出しました。円形の実験台の周りには、$N$ 個の長方形のゼリーが巡回配列状に並べられており、それぞれ特定の高さと幅を持っています。最初のゼリーと最後のゼリーは隣接していることに注意してください。

隣接する2つの親ゼリーを融合させると、高さが親ゼリーの高さの最大値、幅が親ゼリーの幅の最大値である結合ゼリーが生成されます。融合したゼリーは、巡回配列上の親ゼリーがあった場所を置き換え（配列の要素数は1つ減ります）、原理上は再びその隣接するゼリーと融合させることができます。

この融合操作を任意の回数行うことで、ゼリーの面積の総和を最大化したいと考えています。結局のところ、ゼリーの合計面積が大きければ大きいほど、より多くの都市を征服できるのです！

入力

入力の最初の行には、実験台に最初に置かれているゼリーの数 $N$ ($1 \le N \le 3 \cdot 10^5$) が含まれます。

続く $N$ 行は、これらのゼリーを順番に記述しています。$i$ 番目の行には、$i$ 番目のゼリーの高さ $h_i$ と幅 $w_i$ ($1 \le h_i, w_i \le 10^6$) がスペース区切りで含まれます。

出力

融合操作を任意の回数行い、面積の総和を最適に最大化した後の、巡回配列に残っているゼリーの面積の総和を単一の整数で出力してください。

入出力例

入力 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