样例下载

【问题描述】

N 头奶牛要喝水，喝足后才会心满意足地走回牛栏。

只有两个水龙头，所以约翰要把这些奶牛排成两队，并安排好各队的顺序。

每个水龙头同一时刻只能让一头奶牛喝水。

每头奶牛有一个喝水时间 Ai 和走回牛栏的时间 Bi。

约翰太累了，他希望尽早让牛全部回到牛栏，这样他才能去休息。

如何安排两队的顺序才能让他尽早休息呢？

自然地，约翰找到了你。

你只需要告诉他可以去休息的最早时间，也就是所有牛都回到牛栏的最早时刻。

注：第一头喝水的牛开始喝水的时刻记为时刻 0。排在同一队的牛，上一头牛喝完水后，下一头牛立刻可以喝水。每头牛喝完水后立刻往牛栏走。所有的环节中间花费的时间均忽略不计。

【输入格式】

第一行：一个整数 N，表示奶牛的数目；

接下来 N 行，每行两个整数 Ai，Bi，依次表示第 i 头牛的喝水时间和走回牛栏的时间。

【输出格式】

一个整数，表示所有牛都回到牛栏的最早时刻。

【样例输入】

3
2 2
5 3
3 6

【样例输出】

9

【数据范围】

20% 的数据，1 ≤ N ≤ 10

100% 的数据，1 ≤ N, Ai, Bi ≤ 200