题目描述

$TYOI$冬令营准备组织同学们完成一项特殊的双人任务，每两个同学组成一队。

现在冬令营有$m$(保证$m$是偶数)个同学，每个同学都有一个能力值$y$。对于这$m$位同学，$JY$老师十分清楚他们的能力值是多少，其中有$n$种不同的能力值，总共有$x_i$个同学的能力值为$y_i$。保证$x_1+x_2+x_3+.....+x_n=m$。

$JY$老师准备将同学们两两组合，每一对同学完成任务的时间是两位同学的能力值之和。

然后让这$m/2$对同学在同一时间开始做任务，$JY$老师想知道所有同学都完成任务所需要的最短时间是多少呢？

输入格式

第一行输入一个正整数$n$，表示能力的种类数；

接下来输入$n$行，每行输入两个正整数$x$和$y$，表示能力值为$y$的同学数量为$x$。保证所有$x$的总和等于$m$。

输出格式

输出所有同学都完成任务所需要时间的最小值。

3
1 8
2 5
1 2

10

请下载附加样例

请下载附加样例

数据范围

对于$30\%$的数据，$1 \leq n \leq 50$，$x_i<m \leq 10^{10}， \sum x_i = m$，$1 \leq y \leq 1,000,000,000$.

对于$100\%$的数据，$1 \leq n \leq 100,000$，$x_i<m \leq 10^{10}， \sum x_i = m$，$1 \leq y \leq 1,000,000,000$.

附加样例