题目描述

Farmer John 发现，当他的奶牛附近有另一头奶牛提供精神支持时，每头奶牛挤奶会更容易。因此，他希望将他的 $N$ 头奶牛分成 $N/2$ 对。每对奶牛将被引导到谷仓中一个单独的隔间进行挤奶。这些 $N/2$ 个隔间中的挤奶过程将同时进行。

Farmer John 的每头奶牛都有不同的产奶量。如果产奶量分别为 $A$ 和 $B$ 的两头奶牛被配对，那么挤完它们总共需要 $A+B$ 单位时间。

请帮助 Farmer John 确定整个挤奶过程完成所需的最少时间，假设他以最佳方式配对奶牛。

输入格式

输入的第一行包含 $N$（$1 \leq N \leq 100,000$）。

接下来的 $N$ 个整数表示产奶量为 $y_i$ 的奶牛（$1 \leq y_i \leq 1,000,000,000$）。

输出格式

输出 Farmer John 的奶牛挤奶所需的最少时间，假设它们以最佳方式配对。

输入输出样例 #1

输入 #1

4
2 5 5 8

输出 #1

10

说明/提示

在这里，如果产奶量为 8 和 2 的奶牛配对，产奶量为 5 和 5 的奶牛配对，那么两个隔间的挤奶时间均为 10 单位时间。由于挤奶是同时进行的，因此整个挤奶过程将在 10 单位时间后完成。任何其他配对方式都会导致某个隔间的挤奶时间超过 10 单位时间，因此不是最优的。