题目描述

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

输入格式：

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

输出格式：

输出产奶时间的最小值

输入样例#1：

3
1 8
2 5
1 2

输出样例#1：

10

数据范围

1≤N≤100,000
M≤1,000,000,000，M为偶数
1≤y≤1,000,000,000