Neo-Robin Hood

Time limit4sMemory limit256 MB

Summary

Choose a set of politicians to rob and a disjoint set to bribe so that total stolen money covers total bribes, maximizing the number robbed.

Level: Hard8 of 10
Topics: Greedy, Sorting, Binary search, Heap
Solved: No attempts yet

Problem

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 ( $1 \le i \le n$ ) has $m_i$ dollars, and needs $p_i$ 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 choose to do one of the following:

Steal his $m_i$ dollars;
Do nothing to him;
Help him gain political influence, by giving him $p_i$ 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?

Input

The first line of the input contains a positive integer $n$ ( $1 \le n \le 100\,000$ ), the number of politicians. The second line of the input contains $n$ positive integers $m_i$ ( $1 \le m_i \le 10^9$ , for all $1 \le i \le n$ ). The third line of the input contains $n$ positive integers $p_i$ ( $1 \le p_i \le 10^9$ , for all $1 \le i \le n$ ).

Output

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.

Examples3

Example 1
Input
```
5
2 3 4 5 6
1 2 3 4 5
```
Expected output
```
2
```
Example 2
Input
```
4
1 2 4 2
5 6 9 7
```
Expected output
```
0
```
Example 3
Input
```
4
9 19 6 5
20 3 16 19
```
Expected output
```
1
```