Izbori
In our country there are n local parties and i-th party has ai members. In order to make some party to vote for us, we need votes from more than half of its members. In order to win elections, we need votes from more than half of the n parties. What is the minimum number of members we need to bribe in order to win these elections?
Input The first line of the standard input contains positive integer n <= 1000 - number of local parties. Each of the next n lines contains one positive integer ai - number of members of the i-th party (ai <= 10^9).
Output To the standard output write minimal number of bribed members.
Input:
3
6
5
6 Output:
7
Explanation:
If we bribe 4 members from 1. party and 3 members from 2. party, these two parties (of three) will vote for us and we win. It is not possible to win by bribing less then 7 members.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.