题目描述

有 $n$ 头奶牛跑到 FJ 的花园里去吃花儿了，它们分别在距离牛圈 $T_i$（这里指 FJ 到那里需要 $T_i$ 分钟）处吃花，每分钟会吃掉 $D_i$ 朵花，FJ 现在要将它们给弄回牛圈，但是他每次只能弄一头回去，来回用时总共为 $2 \times T_i$ 分钟，在这段时间内，其它的奶牛会继续吃 FJ 的花，速度保持不变，当然正在被赶回牛圈的奶牛不能继续吃了。现在求在最好的方案下奶牛吃掉花的最小朵数。

输入格式

第一行一个正整数 $n$。

下面 $n$ 行，每行两个正整数 $T_i,D_i$。

输出格式

一行一个整数表示答案。

输入输出样例 #1

输入 #1

6
3 1
2 5
2 3
3 2
4 1
1 6

输出 #1

86

说明/提示

样例解释：最优策略是按 $6 \to 2 \to 3 \to 4 \to 1 \to 5$ 的顺序把牛赶回牛圈。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le T_i \le 2 \times 10^6$，$1 \le D_i \le 100$。