题目描述

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

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

在任何时刻，一台机器只能最多处理一个任务。

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

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

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

输入格式

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

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

输出格式

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

样例

输入

2

1 2

90 95

---

3

1 3

1 3

1 3

输出

90

---

3

n<=2000,ta,tb<3000