|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||256 MB||5||4||4||80.000%|
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 chose to do one of the following:
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 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 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.
5 2 3 4 5 6 1 2 3 4 5
4 1 2 4 2 5 6 9 7
4 9 19 6 5 20 3 16 19