You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在步行街中，有 $n$ 间商店买卖同一种商品，第$i$间商店一件商品的收购价和出售价均为 $a_i$ 元。为了防 止过度交易，步行街有一个规定：您在第i间商店最多进行$b_i$ 次交易（一次买或一次卖均计为一次交 易），且每次只能交易一件商品。

您准备通过在步行街中买卖这种商品来赚钱。假如初始时有无限的金钱（也就是说，不会因为钱不够而买不了一件商品），您最多能在步行街中赚到多少总利润？具体来说，“利润”指的是卖出商品获得的金钱总额，减去购买商品花费的金钱总额。

输入格式：

第一行输入一个整数$n$ $（1 \le n \le 10^5）$，表示商店的数量。 对于接下来 $n$ 行，第 $i$ 行输入两个整数 $a_i$ 和$b_i$ （$1 \le a_i , b_i \le 10^6$），分别表示第$i$间商店的商品价格，以及该商店可以交易的最大次数。

输出格式

输出一行一个整数，表示在步行街中赚到的最大总利润。

样例1

输入

4
10 2
30 7
20 4
50 1

输出

100

样例2

输入

2
1 100
1 1000

输出

0

样例解释

对于第一组样例数据，最优方案是在第 $1$ 间商店买入$2$件商品，在第$3$间商店买入$4$件商品，在第 $2$ 间商店卖出 $5$ 件商品，在第 $4$ 间商店卖出 $1$ 件商品。总利润为 $30*5+50*1-10*2-20*4=100$。 对于第二组样例数据，由于所有商店的商品价格都相同，因此无法获得利润。

数据分布

$40\%$ 的数据，$1 \le n \le 100$，$1 \le a_i , b_i \le 100$

$100\%$ 的数据，$1 \le n \le 10^5$，$1 \le a_i , b_i \le 10^6$