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$ 个人需要使用微波炉 $a_i$ 分钟。微波炉不能同时加热多份食物。当午餐被加热后，第 $i$ 个人会立即开始用餐，他需要 $b_i$ 分钟才能将午餐吃完。

请问，这些人应该按照什么顺序排队使用唯一的微波炉，才能让所有人尽可能早地吃完午餐。

输出最后一个人吃完午餐的最早时间;

输入输出格式

输入格式

第一行:单个整数表示 $n$。

第二行到第 $n + 1$ 行: 第 $i+ 1$ 行两个整数表示 $a_i$ 与 $b_i$。

输出格式

单个整数:表示答案

输入输出样例

3
2 2
2 7
3 4

9

5
5 7
1 1
2 6
6 12
3 13

22

数据范围

• $30\%$ 的分数，$1 ≤ n ≤ 10$
• $60\%$ 的分数，$1≤n≤100$
• $100\%$ 的分数，$1≤n≤100,000$
• $1≤a_i≤ 20,000$
• $1≤b_i≤100,000,000$