"Animals generally form groups. Carnivores have a hierarchy, and those that don't manage to get to the top of the food chain will live a life of constant stress. Herbivores have their own problems, like being forced to abandon their own survive enemy attacks. As you can see, being in a group brings no advantages to the individual. Thus, I choose to be the bear, a beast that refuses to form groups with others. It's an animal of isolation that's not at all worried about its solitary lifestyle. Let's not forget that bears get to hibernate as well. Oh, what a wonderful existence. If I'm ever reincarnated, I most certainly would like to be reborn as a bear."
Such are the sentiments of Nate, a nihilistic teenager who shuns the company of others. In fact, the above paragraph was something he wrote for one of his school assignments. Nevertheless, Nate finds some things in the world interesting, such as movies. One day, he watched the movie "Inception" online and proceeded to ask Siri, "What is inception?" to which she replied, "Inception is about dreaming about dreaming about dreaming about dreaming about something or other. I fell asleep." Now Nate wonders, "What if I had a box in a box in a box in a box in a box…" and helplessly fell asleep. After waking up from a short sleep, in his dazed state, Nate forgot the fact that he had no friends (or anyone he even considers an acquaintance), and thought, "Oh yes! I can put a box in a box in a box in a box and troll people!" (One day he realizes his grave mistake and momentarily falls into a state of depression, but that story is a few months away, so let's not get to that right now)
Nate searches his house for boxes, and finds boxes of varying heights and widths.
Conveniently, each box
has a square base of width
and a height of
. A box
can be
put into box
if and only if
and
. Also, from opening one box, there must be
at most 1 other box immediately visible. In other words, he cannot have two boxes
and
both in a box
when
does not contain
and
does not contain
. While smirking to
himself, Nate thinks, "Heheheh… People are going to be mad when they open so many
boxes only to find the last box contains nothing…" While admiring his own genius, he
comes up with a more evil scheme – to maximize the average number of boxes a person
has to open for each giant box. In other words, he wants to find how to store all the
boxes in other boxes such that the number of boxes visible from an outsider's point of
view is minimal (minimize the number of boxes not contained in another box). As Nate
finds this to be a tedious task, he seeks the help of a computer programmer – you.
Input Specification
The first line will contain an integer , the number of boxes Nate has.
The following two lines will each contain integers
and
respectively.
Output Specification
The output should contain one line with one integer, the minimum number of boxes that are not put into another box, while following the other conditions Nate has set.
Constraints
For all subtasks:
Subtask 1 [26%]
.
Subtask 2 [33%]
Subtask 3 [41%]
Subtask 4 [0%]
Sample test cases.
Sample Input
6
10 20 10 40 23 53
20 30 10 30 43 31
Sample Output
2
Explanation for Sample Output
Put box 1 in 4 in 6, box 3 in 2 in 5, then only boxes 5 and 6 are visible (not contained in another box).
Comments