Description
顾韦和苏半夏在玩游戏
苏半夏建立一个一维坐标x,开始时顾韦在x=0处
现有n个指令(d,k)要执行(k是正整数)
每一个指令必须执行且只执行一次
每执行完一个指令后,顾韦都能得到∣2kx+dk∣(∣x∣表示x的绝对值)的分数,且移动到x=x+d的位置
现在顾韦可以任意指定执行指令的顺序,求顾韦能得到的最大分数
第一行一个正整数n
接下来n行各有2个整数di,ki
Output
一行一个整数表示最大总分.
Samples
1
1 1
1
Limitation
对于10%的数据,保证n⩽10
对于另外10%的数据,保证di>0
对于另外10%的数据,保证∑i=1ndi=0
对于100%的数据,保证1⩽n⩽3e5,∣di∣⩽100,1⩽ki⩽100