Description

The class is organizing a comprehensive ability competition. There are $n$ students in the class, and they will be divided into two teams to compete against each other.

The teacher gave Yueyue (pinyin) a list of the comprehensive ability test scores for the whole class and asked him to select exactly half of the students, such that the sum of their test scores is as large as possible without exceeding half of the class's total score. This makes the two teams as balanced as possible. Yueyue, smiling, came to you; please help him write a program.

Input Format

The first line contains an integer representing the number of students $n$.

From line $2$ to line $(n + 1)$, each line contains one integer. The integer on line $(i + 1)$, $a_i$, represents the score of the $i$-th student.

Output Format

Output one integer on a single line representing the answer.

8
77
77
56
77
84
77
56
46

273

Hint

Explanation for Sample 1

The class total score is $550$, and half of the total is $275$. Choosing students with scores $56,77,84,56$ gives a sum of $273$, which is the maximum that does not exceed $275$.

Constraints

For all test points, it is guaranteed that $1 \leq n \leq 100$, $0 \leq a_i \leq 100$, and $n$ is even.

Translated by ChatGPT 5