说明

时间限制：1 Sec 内存限制：256 MB 输入文件：buyall.in 输出文件：buyall.out

小明所在的城镇明天会新开一家商店。从明天起，小明打算每天都去这家店，每天买 $1$ 件商品，直到集齐店里所有商品。镇上只有小明一个人，所以不会有其他人购买商品。

商店共有 $N$ 件商品，第 $i$ 件商品的初始价格为 $A_i$ 元，每天会上涨 $B_i$ 元。也就是说，在开店后的第 $d$ 天购买商品 $i$，需要花费 $A_i + B_i \times d$ 元。

开店当天视为第 $0$ 天。

每件商品只有 $1$ 件库存，不能重复购买同一件商品。

商店会在开店后天数为奇数的日子举办活动（第 $1$、$3$、$5$……天）。在活动日购买商品的人，可以免费额外获得任意 $1$ 件商品，与该商品价格无关。

小明可以安排购买顺序，希望花费最少的钱集齐所有商品。请问集齐 $N$ 件商品至少需要多少钱？

输入格式

第一行，商品数量 $N$。

接下来 $N$ 行：每行给出商品 $i$ 的初始价格 $A_i$ 和每日涨价幅度 $B_i$。

输出格式

输出集齐所有商品所需的最小总花费。

样例

样例 1

3
6 8
2 9
4 7

13

样例说明：

- 第 $0$ 天：花费 $2+9\times0=2$ 元购买商品 $2$。

- 第 $1$ 天：花费 $4+7\times1=11$ 日元购买商品 3。因为是奇数日，活动免费获得商品 $1$。

总计 $2+11=13$。

样例 2

2
6 2
3 3

11

样例说明：

最优：第 $0$ 天买商品 $2$，第 $1$ 天买商品 $1$。

注意以下行为不允许：

- 第 $0$ 天不买，第 $1$ 天买商品 $2$ 并免费拿商品 $1$。

- 第 $0$ 天买商品 $2$，第 $1$ 天再买一次商品 $2$ 并免费拿商品 $1$。

样例 3

8
3 13
18 8
3 14
1 18
3 3
18 12
10 18
15 19

169

数据范围

对于 50% 的数据，$N \le 10$，$A_i,B_i \le 100$。

对于 100% 的数据，$1 \le N \le 2000$，$1 \le A_i,B_i \le 10^5$。