Wesley's Anger Contest 4 Problem 2 - Squirrel Election

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 512M

Authors:

Problem types

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 $N$ $N$ provinces, with the $i^{th}$ $i^{t h}$ province populated by $v_i$ $v_{i}$ voters. If Wesley earns more than half of the votes in the $i^{th}$ $i^{t h}$ province he is awarded with $p_i$ $p_{i}$ points, otherwise Besley will automatically get the $p_i$ $p_{i}$ 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.

Constraints

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:

$1 \le N \le 5\,000$ $1 \leq N \leq 5 000$
$1 \le v_i \le 10^9$ $1 \leq v_{i} \leq 10^{9}$
$0 \le p_i \le 5\,000$ $0 \leq p_{i} \leq 5 000$
The total sum of $p_i$ $p_{i}$ is at least $1$ $1$ and at most $5\,000$ $5 000$ .

Subtask 1 [20%]

$v_i = 1$ $v_{i} = 1$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains an integer $N$ $N$ indicating the number of provinces in the squirrel nation.

The next $N$ $N$ lines each contain two integers $v_i$ $v_{i}$ and $p_i$ $p_{i}$ separated by a space.

Output Specification

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

Copy

Sample Output 1

Copy

Sample Explanation 1

By forcing a victory with the first two provinces, Wesley can instantly gain $13$ $13$ points and win the election. Note that $8$ $8$ points will result in a tie, which will not be enough.

Sample Input 2

Copy

Sample Output 2

Copy

Sample Explanation 2

By forcing a victory with the first, fifth, and sixth provinces, Wesley can win the election by threatening $3+1+2 = 6$ $3 + 1 + 2 = 6$ voters.

Comments

1

NoOneofConsequence commented on April 6, 2021, 1:15 p.m.

I like how in Sample Explanation 2, it's just made clear that Wesley threatens voters.

3

henrybaolol9 commented on April 6, 2021, 1:50 p.m.

that's just propaganda. he can win the election because he's a very influential candidate.

4

crackersamdjam commented on April 6, 2021, 2:00 p.m.

The voting doesn't even matter since those who vote decide nothing. It's those who count the vote who decide everything.