题目描述

星期四到啦!计算机学院 ACM 集训队决定去 KFC 疯狂星期四!
因为集训队之后还有训练计划,大家决定速战速决,这家 KFC 有两个点餐窗口,每个窗口同一时刻只能给一个人点餐,因为每个人吃的套餐不同,所以点餐时间是因人而异的,另外每个人用餐时间也是因人而异的。
集训队的疯狂星期四计划是这样的:先把所有队员分成两队,每个队伍安排好队员的先后顺序,然后一号队伍去一号点餐窗口,二号队伍去二号点餐窗口,每个人点完餐后找座位立刻开吃,所有人吃完后回学校继续训练。
现在知道了每个队员的点餐用时和用餐用时,集训队希望能够安排一种最佳的分队和排队方案使得每个队员都用完餐的用时最少。
注意:每个队员只能被分在一个队伍里;两个窗口是分别独立的,互不影响;队员点完餐后直接开吃(中间没有延迟);虽然是疯狂星期四,这家 KFC 里只有集训队队员,没有其他人。


输入格式

第一行一个整数 N(1≤N≤200),代表总共有 N 个队员。
接下来 N 行,每行两个整数 a_i,b_i (1≤a_i,b_i≤200),表示第 i 个队员的点餐时间和用餐时间。


输出格式

一个整数表示所有队员用完餐的最少耗时。


样例数据

输入

5
2 2
7 7
1 3
6 4
8 5

输出

17

备注

采用动态规划的方法进行求解。
样例方案如下:
数字表示队员编号,队列按从左到右顺序
窗口一:2 4 1
窗口二:5 3


操作

评测记录

优秀代码

信息

时间限制: 200s
内存限制: 512MB
评测模式: Normal

题解