题目描述

有两台机器 A、B 用于加工零件。每个零件必须先在 A 上加工，再在 B 上加工。零件 $i$ 在 A 上加工需要 $a_i$ 时间，在 B 上加工需要 $b_i$ 时间。同一时刻每台机器最多加工一个零件，且所有零件在两台机器上的加工顺序必须相同（即每个零件先 A 后 B）。求加工完全部零件所需的最小总完工时间。

输入格式

第一行一个整数 $n$（$1 \le n \le 1000$），表示零件数量。

接下来 $n$ 行，每行两个整数 $a_i, b_i$（$1 \le a_i, b_i \le 10^9$），用空格隔开，表示第 $i$ 个零件在两台机器上的加工时间。

输出格式

一行一个整数，表示最小总完工时间。

样例

样例输入

3
3 1
2 5
4 2

样例输出

10

数据范围与提示

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a_i, b_i \le 10^9$。答案可能超过 32 位整数范围，请使用 64 位整数（long long）。

提示：本题可使用 Johnson 法则贪心求解——若 $a_i < b_i$，将该零件放在前面并按 $a_i$ 升序排列；若 $a_i \ge b_i$，将该零件放在后面并按 $b_i$ 降序排列。然后按此顺序依次加工，模拟两台机器的完工时间即可。