SEERC 2021

Neo-Robin Hood

There are n aspiring politicians in Neverland. They are wealthy, but not wealthy enough to gain political influence. Since Neverland is a financially transparent haven, we know the bank statements of each politician: the i-th politician (1in) has mi dollars, and needs pi more dollars to achieve his political goals.

You are the infamous modern superhero Neo-Robin Hood. You earn your living by stealing from the rich and wealthy, in order to help... well, whoever promises to help you back. For each of the n politicians you can chose to do one of the following:

  1. Steal his mi dollars;
  2. Do nothing to him;
  3. Help him gain political influence, by giving him pi dollars.

But your services don’t come for free. Once you help a politician gain political influence, he is bound to help you cover-up one of your thefts so that you won’t get in trouble – for instance, by providing an alibi. In turn, you are also bound to not steal his money in the future.

Initially you start with no money. Your task is to rob as many politicians as possible; however, you can’t afford to get caught, so you need a politician to account for each crime you commit.

What is the maximum number of people you can rob?


The first line contains a positive integer n (1n100 000), the number of politicians. The second line contains n positive integers mi (1mi109, for all 1in). The third line contains n positive integers pi (1pi109, for all 1in).


Output a single non-negative integer, the maximum number of people that you can steal from.

Note that you do not have to maximize your own wealth, but rather the number of people that you are stealing from.

Time limit 4 seconds
Memory limit 256 MiB
Input example #1
2 3 4 5 6
1 2 3 4 5
Output example #1
Input example #2
1 2 4 2
5 6 9 7
Output example #2
Input example #3
9 19 6 5
20 3 16 19
Output example #3
Source 2020 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, May 23, Problem L