题目描述

某实验室有n台设备需进行校准。每台设备需先进行初始化设置（耗时R_i分钟），之后自动运行检测程序（耗时T_i分钟）。实验室管理员需按顺序依次初始化设备，但设备检测可并行执行。请设计调度顺序，使所有设备完成检测的总时间最短。

输入格式

第一行：整数n（1 ≤ n ≤ 1000）
接下来n行：每行两个整数R_i和T_i（1 ≤ R_i, T_i ≤ 10000），分别表示初始化时间和检测时间

输出格式

总完成时间的最小值。

样例数据

input

4  
5 12  
2 8  
3 10  
1 5

output

18