問題文

$N$ 個の椅子が前後一列に並んでいます。これらの椅子にははじめ誰も座っていません。

これから $N$ 人の学生が一人ずつ順番に椅子に座っていきます。$i$ 番目に椅子に座る学生には正整数 $A_i$, $B_i$ が割り振られています。

各学生はその時点で誰も座っていない椅子のうち、最も前または最も後ろにある椅子に座ります。

最終的に各 $i$ 番目の学生が前から $P_i$ 番目の椅子に座るとき、学生の座り方は $P$ であるといい、座り方 $P$ における $i$ 番目の学生の嬉しさ $f_P(i)$ を $f_P(i) = \sum_{j : P_j < P_i}A_iB_j $ と定めます。

すべての座り方 $P$ の中で学生のうれしさの総和 $\sum_{i = 1}^{N}f_P(i)$ が最大となるときの値を求めてください。

入力

$N$
$A_1 \ B_1$
$\vdots$
$A_N \ B_N$

• 入力される値はすべて整数
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^4$
• $1 \le B_i \le 10^4$

出力

答えを出力してください。

サンプル

3
7 3
10 1
2 5

92

7
3 6
1 5
4 3
1 5
5 8
9 9
2 7

584

1
1 1

0