3775. 任务

【题目描述】

这里本来应该有一些有趣的题目背景，但我是懒狗，所以大家自己脑补一下。

【题目描述】

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

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

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

3. 任务 $i(0<i\le n)$ 可以被处理当且仅当每个任务 $j(j<i)$ 已经被完成或者正在进行。

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

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

【输入格式】

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

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

【输出格式】

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

【样例输入 1】

2
1 2
90 95

【样例输出 1】

90

【样例输入 2】

3
1 3
1 3
1 3

【样例输出 2】

3

【样例说明】

第一组数据：让 $B$ 机器完成任务 $1$ 同时让 $A$ 机器完成任务 $2$。

第二组数据：让 $A$ 机器完成所有的任务。

大洋里。

【数据规模与约定】

对于 $30\%$ 的数据，$1\le n\le 20, 0 < t_A, t_B \le 30$。

对于 $70\%$ 的数据，$1\le n\le 200, 0 < t_A, t_B \le 300$。

对于 $100\%$ 的数据，$1\le n\le 2000, 0 < t_A, t_B \le 3000$。

【来源】

经典问题。