Description

顾韦和苏半夏在玩游戏

苏半夏建立一个一维坐标$x$,开始时顾韦在$x=0$处

现有$n$个指令$(d,k)$要执行($k$是正整数)

每一个指令必须执行且只执行一次

每执行完一个指令后,顾韦都能得到$|2kx+dk|$($|x|$表示$x$的绝对值)的分数,且移动到$x=x+d$的位置

现在顾韦可以任意指定执行指令的顺序,求顾韦能得到的最大分数

Format

Input

第一行一个正整数$n$

接下来n行各有2个整数$d_{i}$,$k_{i}$

Output

一行一个整数表示最大总分.

Samples

1
1 1

1

Limitation

对于$10\%$的数据,保证$n \leqslant 10$

对于另外$10\%$的数据,保证$d_{i}>0$

对于另外$10\%$的数据,保证$\sum_{i=1}^{n} d_{i} =0$

对于$100\%$的数据,保证$1 \leqslant n \leqslant 3e5,|d_{i}| \leqslant 100,1 \leqslant k_{i} \leqslant 100$