题目描述

某个字符集中有\(n\)种字母，第\(i\)种字母的价值为\(v_i\)/个，\(i = 1 \cdots n\)。注意\(v_i\)可能是负数。
现要构造一个任意长度的字符串\(s\)，要求第\(i\)种字母的出现次数不得超过\(num_i\)。定义该串的价值为\(\sum_{i=1}^{\lvert s \rvert} {i \times v_{s_i}}\)，即\(k \times \)第\(k\)位字符的价值，然后对\(k=1 \cdots \lvert s \rvert\)求和。（其中符号\(\lvert s \rvert\)表示字符串\(s\)的长度）
求所有可以构造出的串中，最大的价值是多少。注意由于这个串可以是空的，所以价值一定不会小于0。

输入格式

第一行一个整数\(n\)，表示字母的种类数；
接下来\(n\)行，每行两个正数\(v_i,num_i\)，含义见上。

输出格式

一个整数，表示最大的串的价值。

样例

输入

3
-5 3
2 1
1 1

输出

5

数据规模、时空限制

对于30%的数据，\(n \leq 10\)；
对于另外20%的数据，\(v_i \geq 0\)；
对于100%的数据，\(n \leq 100000, \quad |v_i| \leq 100, \quad num_i \leq 10\)。
时间限制1s，空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人：于剑