#MX89. Meal

Meal

题目描述

下课铃终于响了,你和一群朋友(共 NN 人)一起冲到食堂。因为你们到的非常早,现在食堂窗口前面还没有人。食堂共有两个窗口。你们每个人打饭会耗时 aia_i ,打完立刻去座位上吃饭会耗时 bib_i ,由于你们吃完饭要一起打球,所以你们希望最后一个人吃完饭的时间尽可能早。现在,你要安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

输入格式

第一行一个整数 NN ,表示共有 NN 人。

接下来 NN 行,每行两个整数 ai,bia_i,b_i ,表示每个人打饭和吃饭的用时。

输出格式

一个整数,表示所有人吃完饭的最早时间。

数据规模与约定

对于 20% 的数据,N≤5N\leq 5 。

对于 40% 的数据,N≤20N\leq 20 。

对于另外 20% 的数据,每个人吃饭时间都一样。

对于 100% 的数据,1≤N,ai,bi≤5001\leq N,a_i,b_i\leq 500 。

样例 1 输入

5
2 2
7 7
1 3
6 4
8 5

样例 1 输出

17

样例 2

见下发文件,满足每个人吃饭时间相同。

样例 3

见下发文件。