You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

N人来到了游乐场准备游玩。但奈何游乐场太小，只有两个咨询购票窗口，已知第i个人的咨询购票时长为C[i]，且咨询购票结束后立刻就进入游乐场游玩。

由于每个人游玩的项目不尽相同，所以游玩花费的时间也是可能有所不同的，我们记每个人在游乐场里面的游玩时间记为T[i]。

现在这N个人同时在0时刻到达游乐场，给定了每个人的购票时间C[i]和游玩时间T[i]，每个人只能选择站在某一个窗口排队。请问如何安排这N个人的排队窗口，使得所有人游玩结束的时间尽可能的早，请编程输出游玩最早结束时间。

输入格式

第一行一个整数N，代表总共有N个人。

以下N行，每行两个整数 Ci，Ti。依次代表第i个人的购票时间和游玩时间。

输出格式

一个整数，代表所有人游玩结束的最早时刻。

样例 #1

样例输入 #1

5
2 2
7 7
1 3
6 4
8 5

样例输出 #1

17

数据范围

对于30%的数据：N<=25，B[i]<=200。

对于70%的数据：N<=100，B[i]<=200。

对于100%的数据：N，A[i]，B[i]<=200。