题目描述

农夫约翰有 M（M ≤ 10^9）头奶牛，每头奶牛有一个产奶量。将这些奶牛两两配对，每对奶牛的产奶时间为两头奶牛产奶量的总和。现在这 M/2 对奶牛同时产奶，问所需的最短时间是多少（M 保证为偶数）。

输入格式

• 第 1 行：正整数 N（1 ≤ N ≤ 10^5）。
• 接下来 N 行：每行两个正整数 x 和 y，表示有 x 头奶牛的产奶量为 y（1 ≤ y ≤ 10^9）。
• 保证所有 x 的总和等于 M。

输出格式

输出使所有配对同时产奶时所需的最小时间。

输入样例 #1

3  
1 8  
2 5  
1 2

输出样例 #1

10

题目说明

样例中奶牛的产奶量为 8, 5, 5, 2。
配对为 (8, 2) 与 (5, 5)，两对的时间均为 10，因此最短时间为 10。