题目描述

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

${M}$保证为偶数

输入格式

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

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

输出格式

输出产奶时间的最小值

样例

输入样例

3
1 8
2 5
1 2

输出样例

10

提示

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

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