样例下载

【问题描述】

有 N 个零件需要加工。零件编号为 1 ~ N。每个零件加工需要经过两道工序：首先将表面打磨光滑，然后喷涂油漆。

只有 1 台打磨机和 1 台喷涂机。每台机器在一个时刻只能对一个零件进行作业。

打磨机打磨零件 i 需要时间为 Ai.

喷涂机喷涂零件 i 需要时间为 Bi.

问：所有零件加工完成最少需要多长时间？

机器切换零件的时间可以忽略不计，并且打磨后的零件可以过一会再喷涂油漆。零件打磨的顺序和喷漆的顺序不一定相同。

【输入格式】

第一行：一个整数 N；

接下来 N 行，每行两个整数 Ai，Bi。

【输出格式】

一个整数，表示答案。

【样例输入】

3
2 2
5 3
3 6

【样例输出】

14

【样例解释】

方案可能不唯一，以下是一种可能方案：

零件 3 先打磨，花费 3 个时间单位，打磨完后接着喷漆，花费 6 个时间单位。喷漆在第 9 个时刻结束。

零件 2 在零件 3 打磨完接着进行打磨，花费 5 个时间单位，打磨在第 8 个时刻结束，此时零件 3 喷漆还未结束，等待 1 个时间单位，零件 3 喷漆结束，零件 2 开始喷漆，花费 3 个时间单位，喷漆在第 12 个时刻结束。

零件 1 在零件 2 打磨完后接着进行打磨，花费 2 个时间单位，打磨在第 10 个时刻结束，此时零件 2 喷漆还未结束，等待 2 个时间单位，零件 2 喷漆结束，零件 1 开始喷漆，花费 2 个时间单位，喷漆在第 14 个时刻结束。

此时零件全部加工完毕，共花费 14 个时间单位。

【数据范围】

15% 的数据：$1 ≤ N ≤ 10$

40% 的数据：$1 ≤ N ≤ 100$

100% 的数据：$1 ≤ N ≤ 3·10^4, 1 ≤ Ai, Bi ≤ 5·10^4$