The squirrel nation is holding a (totally not rigged) election! There are only two candidates in this election: Wesley and
Wesley Besley. To reign supreme over the nation, Wesley will do anything to make sure he wins.
The nation is split into provinces, with the province populated by voters. If Wesley earns more than half of the votes in the province he is awarded with points, otherwise Besley will automatically get the points. After the voting process, whichever candidate earns the most points in the end wins (ties do not count as a victory). Every squirrel must cast a vote for either of the candidates.
As a very influential candidate, Wesley can force any number of voters to vote for him. Assuming every voter in the nation initially planned to vote for Besley, what is the minimum amount of voters Wesley needs in order to win the election?
For this problem, Python users are recommended to use PYPY over CPython.
For this problem, you will NOT be required to pass all the samples to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.
For all subtasks:
The total sum of is at least and at most .
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
The first line contains an integer indicating the number of provinces in the squirrel nation.
The next lines each contain two integers and separated by a space.
This problem is graded with an
identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a
\n character and that there are no trailing spaces.
On a single line, output an integer representing the minimum amount of voters Wesley needs.
Sample Input 1
5 1 5 1 8 1 0 1 1 1 2
Sample Output 1
Sample Explanation 1
By forcing a victory with the first two provinces, Wesley can instantly gain points and win the election. Note that points will result in a tie, which will not be enough.
Sample Input 2
6 4 5 9 8 1 0 1 1 1 2 3 4
Sample Output 2
Sample Explanation 2
By forcing a victory with the first, fifth, and sixth provinces, Wesley can win the election by threatening voters.