Time Limit: 1000 MSMemory Limit: 65536 K


描述

现在有两台机器A和B。有个任务,编号你必须把每个任务安排到一台机器上处理,同时需要满足以下一些条件。

(1) 你必须把每个任务安排到任意一台机器上处理。

(2) 在任何时刻,一台机器只能最多处理一个人任务。

(3) 任务可以被处理当前仅当每个任务已经被完成或者正在进行。

(4) 一个任务如果在一台机器上进行,它是不能被打断的。

请你算算最少完成任务的时间。

输入

第一行一个
每一组第一行一个整数表示任务的个数。

接下来行,每行两个整数,表示完成每个任务在两台机器上花的时间

输出

输出最早完成任务的时间。

样例输入

4

1
1 2

2
1 2
2 1

2
1 2
90 95

3
1 3
1 3
1 3

样例输出

1

1

90

3

lcy的良心解释

样例解释:

第一组数据:让A机器完成任务1。

第二组数据:让A机器完成任务1同时让B机器完成任务2。

第三组数据:让B机器完成任务1同时让A机器完成任务2。

第四组数据:让A机器完成所有的任务。