T2 加工车间（factory）

题目描述

小真在一家零件加工厂打工。车间里有一台加工设备，送来的零件必须排队加工。

共有 $n$ 个零件。第 $i$ 个零件在时刻 $a_i$ 才送到车间，一旦开始加工，需要连续占用设备 $t_i$ 个单位时间，加工过程中不能被打断。

设备在同一时刻只能加工一个零件。每当设备空闲时，小真会从所有已经送到、且还没有加工的零件中，选择加工耗时最短的那个开始加工（若耗时相同，任意选择）。如果此时还没有任何零件送到，设备就空等到下一个零件送到。

请你帮忙算出：所有零件加工完成时刻之和。

输入文件 factory.in，输出文件 factory.out。

输入格式

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

接下来 $n$ 行，每行两个整数 $a_i,t_i$，分别表示第 $i$ 个零件的送达时刻与加工耗时。

输出格式

输出共一行一个整数，表示所有零件加工完成时刻之和。

样例 1 输入

4
1 3
2 5
4 2
6 1

样例 1 输出

29

样例 1 解释

• 时刻 $1$ 设备开工，加工零件 $1$，时刻 $4$ 完成；
• 此时零件 $2$、$3$ 已送到，选耗时更短的零件 $3$，时刻 $6$ 完成；
• 零件 $4$ 在时刻 $6$ 送到，立即开始加工，时刻 $7$ 完成；
• 最后加工零件 $2$，时刻 $12$ 完成。

完成时刻之和为 $4+6+7+12=29$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 10$。
• 对于另 $30\%$ 的数据，保证 $a_i=0$。
• 对于 $100\%$ 的数据，保证 $1 \le n \le 2\times 10^5$，$0 \le a_i,t_i \le 10^9$。