Balanced Team Selection

A class is organizing a comprehensive ability competition. There are n students in the class and the class is to be divided into two teams.

The teacher provided Yueyue with the test scores of all students and asked him to select exactly half of the students such that the sum of their scores does not exceed half of the total score of the class, and is as high as possible. In this way, the strengths of the two teams will be as balanced as possible.

More formally, let there be n students with scores \(a_1, a_2, \dots, a_n\). Let \(T = \sum_{i=1}^{n} a_i\). You need to choose exactly \(\frac{n}{2}\) scores whose total sum \(S\) satisfies \(S \leq \frac{T}{2}\) and \(S\) is maximized. You are required to output this maximum possible sum \(S\).

Note: You can assume \(n\) is even.

inputFormat

The first line contains an integer n (\(n\) is even), representing the number of students.

The second line contains n space-separated integers \(a_1, a_2, \dots, a_n\) representing the scores of the students.

outputFormat

Output a single integer, the maximum possible sum \(S\) of the chosen students' scores such that \(S \leq \frac{T}{2}\) and exactly \(\frac{n}{2}\) students are selected.

sample

4
1 2 3 4

5