描述

有 \(N\) 个村庄，你需要给每个村庄送一封信

设你依次送达的村庄是 \(A_1\), \(A_2\), ..., \(A_N\) ， \(A\) 是 \(1\) 至 \(N\) 的一个排列

记 \(X_{A_i}=i\) ，对于 \(i\) 号村庄，你会获得 \(K_i*(E_i-X_i)\) 的收益（去早得钱，去晚赔钱）

合理安排 \(A\) 求最大收益

输入

第一行一个正整数 \(N\)

接下来 \(N\) 行每行两个正整数 \(K_i\), \(E_i\)

输出

一行一个整数为最大收益

样例

输入

3
2 1
3 3
1 3

输出

4

范围

25% \(N\leq 20\)

50% \(N\leq 1000\)

100% \(N\leq 10^6\), \(K_i\leq 10^6\), \(E_i\leq N\)

限制

1s

128M