You are given two sequences of positive integers a1, a2, ..., an and b1, b2, ..., bn of length n each. You are to write a program which finds k such that ak to the power of bk is maximal.

Input

The first line of input contains a positive integer n, not greater than 10000. In the second line you are given a set of positive integers ai separated by spaces, and in the third line – integers bi. All numbers in both sequences are not greater than 10000. It is guaranteed that all power values are different.

Output

The output must contain one number – the answer to the problem.

Score

The score to this problem is equal to (1000 - t), where t is the time used by your solution, in milliseconds. If your solution works for more than 1 second then you get 0 points.

Example

Input:
5
1 2 2 3 3
100 1 3 2 1

Output:
4