CQOJ

问题 3293 --meal

3293: meal

时间限制: 1 Sec 内存限制: 256 MB
提交: 2 解决: 2
[提交][状态][讨论版][命题人:]

下课铃终于响了，你和一群朋友（共

N

人）一起冲到食堂。因为你们到的非常早，现在食堂窗口前面还没有人。食堂共有两个窗口。你们每个人打饭会耗时ai，打完立刻去座位上吃饭会耗时bi，由于你们吃完饭要一起打球，所以你们希望最后一个人吃完饭的时间尽可能早。现在，你要安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

第一行一个整数N，表示共有 $N$ 人。

接下来 $N$ 行，每行两个整数ai $, bi$ ，表示每个人打饭和吃饭的用时。

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

对于20%的数据， $N \leq 5$ 。

对于40%的数据， $N \leq 20$ 。

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

对于100%的数据， $1 \leq N, ai, bi \leq 500$ 。