题目描述

终末地中有 $n$ 个待开发的基建设施。由于人手有限，你在任意时刻只能同时开发 一个 基建设施。

第 $i$ 个基建设施的开发需要 $a_i$ 个单位时间；当该设施开发完成后，在之后的每一个单位时间内，都会持续产出价值为 $b_i$ 的养成材料。

为了尽可能快地完成所有基建设施的开发，你在完成一个设施的开发后，会立即投入到下一个设施的开发中，中途不出现空闲时间。

在经过总计 $\sum a_i$ 个单位时间、所有设施均开发完成时，求在此过程中 已经产出的养成材料的最大总价值。

输入格式

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

接下来 $n$ 行，每行包含两个由空格隔开的正整数 $a_i, b_i$。

输出格式

输出一个整数，表示答案。

样例 1 输入

5
2 5
2 3
3 4
1 5
3 2

样例 1 输出

120

样例 1 解释

按照 $4 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 5$ 的顺序依次开发各个基建设施，可以使得答案最大。

各基建设施的参数如下：

总开发时间为

依次完成各设施后的产出情况如下：

• 设施 4 在第 $1$ 个单位时间完成，此后还能工作 $10$ 个单位时间，贡献

  $$10 \times 5 = 50$$

• 设施 1 在第 $3$ 个单位时间完成，此后还能工作 $8$ 个单位时间，贡献

  $$8 \times 5 = 40$$

• 设施 2 在第 $5$ 个单位时间完成，此后还能工作 $6$ 个单位时间，贡献

  $$6 \times 3 = 18$$

• 设施 3 在第 $8$ 个单位时间完成，此后还能工作 $3$ 个单位时间，贡献

  $$3 \times 4 = 12$$

• 设施 5 在第 $11$ 个单位时间完成，之后不再有剩余时间，贡献为 $0$。

因此，养成材料的总价值为

可以证明不存在比该顺序更优的开发方案，因此答案为 $120$。

样例 2

见选手目录下的 construction/construction2.in 和 construction/construction2.ans。

该测试用例满足测试点 $1\sim 3$ 的约束条件。

样例 3

见选手目录下的 construction/construction3.in 和 construction/construction3.ans。

该测试用例满足测试点 $6\sim 10$ 的约束条件。

评测数据规模

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5, 1 \le a_i,b_i \le 10^3$。

点此下载大样例