题目描述

有$\red{M(M}$为偶数)头奶牛，每头奶牛有一个产奶量，将这些奶牛两两配对，每对奶牛的产奶的时间为两头奶牛产奶量的总和。现在这$\red{M/2}$对奶牛同时产奶，问所需的最短时间是多少?

$\red{M}$保证为偶数

输入格式

第一行为一个正整数$\red{N}$

接下来有$\red{N}$行，每行两个正整数$\red{x}$和$\red{y，}$表示有$\red{x}$头奶牛的产奶量为$\red{y}$。保证所有$\red{x}$的总和等于$\red{M}$

输出格式

输出产奶时间的最小值

样例

输入样例

3
1 8
2 5
1 2

输出样例

10

提示

奶牛的产奶量分别为$\red{8,5,5,2}$。

让$\red{8}$和$\red{2}$配对，$\red{5}$和$\red{5}$配对，则产奶时间分别为$\red{10,10，}$所以这两对奶牛同时产奶的时间为$\red{10.}$