题目描述

有 $m$ 位同学，其中 $m$ 是偶数。他们的能力值共有 $n$ 种，第 $i$ 种能力值为 $y_i$，具有这个能力值的同学有 $x_i$ 位，且 $\sum_{i=1}^{n}x_i=m$。

需要把所有同学分成 $m/2$ 队，每队恰好两人，每位同学恰好属于一队。两位同学完成任务所需的时间，等于他们的能力值之和。

所有队伍同时开始任务，各队独立完成。求一种分队方式，使所有同学都完成任务的时刻尽可能早，并输出这一时刻。

输入格式

从标准输入读入数据。

第一行包含一个正整数 $n$，表示能力值的种类数。

接下来 $n$ 行，第 $i$ 行包含两个正整数 $x_i,y_i$，表示有 $x_i$ 位同学的能力值为 $y_i$。不同种类的能力值互不相同，输入不保证按能力值排序。总人数 $m$ 由所有 $x_i$ 相加得到，不单独输入。

输出格式

向标准输出输出一个整数，表示所有同学都完成任务所需时间的最小值。

数据范围

对于所有数据，$1\le n\le 100000$，$1\le y_i\le 10^9$，$1\le x_i<m\le 10^{10}$，$\sum_{i=1}^{n}x_i=m$，且 $m$ 为偶数。不同 $y_i$ 两两不同。

子任务

样例 1

3
1 8
2 5
1 2

10

样例 1 说明

把能力值为 $2$ 和 $8$ 的同学分为一队，另外两位能力值为 $5$ 的同学分为一队，两队都在时刻 $10$ 完成。四人的能力值之和为 $20$，两队的耗时之和始终为 $20$，因此较慢的一队不可能早于时刻 $10$ 完成。