Problem Statement

Helia is playing an RPG. In this RPG, the game progresses by leveling up your allied monsters.
Helia has a party of \(N\) monsters and wants to level them up.

To level up, a monster fights an enemy monster one-on-one and gains half of the enemy's level, rounded down. (This is added to the level of the monster that fought.)
For example, when your monster's level is \(1\) and the enemy monster's level is \(5\),
your monster's level becomes \(3\) after the fight.
Since Helia will win by making full use of items, assume that every fight can be won regardless of the level difference.

There is a hunting ground where enemy monsters are arranged in a circle in clockwise order, and once the first monster to fight is decided, you can fight each of them exactly once in clockwise order.
(The first monster to fight can be chosen freely.)
For each fight, Helia sends out the monster in the party with the lowest level at that time; if there are multiple such monsters, the one among them that has fought the fewest battles is sent out.
Suppose that all monsters in this hunting ground are defeated. When the first monster to fight in the hunting ground is chosen so that the largest number of battles fought by any monster in the party is minimized, find that largest number of battles.

Note: The time limit may be tight unless you use a fast language.

Input

\(N\)
\(A_1\ A_2\ \dots\ A_N\)
\(B_1\ B_2\ \dots\ B_N\)

\( N\ (1 \leq N \leq 1500) \) is the number of monsters in the party.
\( A_i\ (1 \leq Ai \leq 10000, 1 \leq i \leq N) \) is the level of each monster in your party.
\( B_i\ (1 \leq Bi \leq 10000, 1 \leq i \leq N) \) is the level of each enemy monster in the hunting ground.

The number of monsters in the hunting ground is the same as the number of monsters in your party.
They are listed in clockwise order.

Output

Output the number as a string.
Print a newline at the end.

Sample

3
6 1 5
9 2 7

2

5
6 1 5 9 2
7 7 9 4 4

2