问题描述

高桥君最近迷上了射击。

高桥君参加了一个比赛，目标是射击掉所有 $N$ 个气球，并使得所得分数尽量小。

每个气球都有一个从 $1$ 到 $N$ 的编号，气球 $i (1 ≦ i ≦ N)$ 在比赛开始时位于高度 $H_i$，每过 $1$ 秒高度增加 $S_i$。

高桥君可以在比赛开始时打破一个气球，并且每过 $1$ 秒可以打破一个气球。高桥君可以自由决定打破气球的顺序。

对于每个被打破的气球，都会产生相应的惩罚。惩罚大小等于该气球被打破时的高度。高桥君最终得分是所有气球惩罚中的最大值。

请计算高桥君可能获得的最小得分。

输入

输入以以下格式从标准输入中给出。

$N$ $H_1$ $S_1$ $H_2$ $S_2$ : $H_N$ $S_N$

• 第 $1$ 行为一个整数 $N (1 ≦ N ≦ 100,000)$，表示气球的个数。
• 第 $2$ 行至第 $N$ 行描述了每个气球的信息。第 $i (1 ≦ i ≦ N)$ 行包含两个整数 $H_i (1 ≦ H_i ≦ 1,000,000,000)$ 和 $S_i (1 ≦ S_i ≦ 1,000,000,000)$，以空格分隔。表示气球 $i$ 在比赛开始时的高度为 $H_i$，每过 $1$ 秒高度增加 $S_i$。

部分分

本问题设有部分分。

• 若对于数据集 $1$，满足 $N ≦ 50$、$H_i ≦ 100,000$、$S_i ≦ 2,000$，则可获得 $30$ 分。
• 若对于额外约束条件下的数据集 $2$，则除上述部分分外额外可获得 $70$ 分。

输出

请输出高桥君可能获得的最小得分，以一行输出。输出最后要换行。

示例输入1

4
5 6
12 4
14 7
21 2

示例输出1

23

例如，按照以下顺序打破气球：

• 竞赛开始时打破气球 $3$。气球 $3$ 的惩罚是 $14 + 7 × 0 = 14$。
• 过了 $1$ 秒后打破气球 $4$。气球 $4$ 的惩罚是 $21 + 2 × 1 = 23$。
• 过了 $2$ 秒后打破气球 $2$。气球 $2$ 的惩罚是 $12 + 4 × 2 = 20$。
• 过了 $3$ 秒后打破气球 $1$。气球 $1$ 的惩罚是 $5 + 6 × 3 = 23$。

因此，高桥君的得分为 $23$，这是可能的最小值。

示例输入2

6
100 1
100 1
100 1
100 1
100 1
1 30

示例输出2

105