题目描述

有 $n$ 个人要用一台微波炉加热午餐，其中第 $i$ 个人需要使用微波炉 $a_i$ 分钟。微波炉不能同时加热多份食物。当午餐被加热后，第 $i$ 个人会立即开始用餐，他需要 $b_i$ 分钟才能将午餐吃完。

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

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

输入格式

• 第一行：单个整数表示 $n$
• 第二行到第 $n+1$ 行：第 $i+1$ 行两个整数表示 $a_i$ 与 $b_i$。

输出格式

• 单个整数：表示答案

3
2 2
2 7
3 4

9

样例解释 1

先安排2 7，然后是3 4，最后是2 2

数据范围

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