题目描述

有 $N$ 个巨人，每个巨人都有唯一的编号 $1, 2, \dots, N$ 。当巨人 $i$ 站在地面上时，其肩部高度为 $A_i$ ，头部高度为 $B_i$ 。

你可以选择一个排列 $P = (P_1, P_2, \dots, P_N)$ ，并按照以下规则依次叠放巨人：

首先，让巨人 $P_1$ 站在地面上，此时其肩部高度为 $A_{P_1}$ ，头部高度为 $B_{P_1}$ 。
对于 $i = 1, 2, \dots, N - 1$ ，令巨人 $P_{i+1}$ 站在巨人 $P_i$ 的肩膀上。如果巨人 $P_i$ 的肩部高度为 $t$ （相对于地面），则巨人 $P_{i+1}$ 的肩部高度变为 $t + A_{P_{i+1}}$ ，头部高度变为 $t + B_{P_{i+1}}$ 。

求经过合理排列后，最上面那个巨人（即 $P_N$ ）的头部高度能达到的最大值。

输入格式

第一行包含一个整数 $N$ ( $2 \le N \le 2 \times 10^5$ )。

接下来 $N$ 行，每行包含两个整数 $A_i$ 和 $B_i$ ( $1 \le A_i \le B_i \le 10^9$ )。

输出一个整数，表示能达到的最大头部高度。

一种最优排列为 $(2, 1, 3)$ ：

因此，最大头部高度为 $18$ 。