Get Maximum Stability

Choose any non-empty subset of servers; its stability is the minimum availability multiplied by the sum of reliability. First maximize the exact integer stability, then take it modulo 1000000007. The source's second example output 5 came from an unrelated explanation; it is corrected to 456 according to the definition.

输入格式

The first line contains n, the second line reliability, and the third line availability. 2≤n≤100000; every value is in 1..1000000.

输出格式

Output a single integer, the answer.

样例 1

输入：

3
1 2 2
1 1 3

输出：

6

样例 2

输入：

6
75 104 72 72 8 125
1 2 2 1 2 1

输出：

456

样例 3

输入：

2
2 3
5 5

输出：

25

样例说明

The answers are 6, 456 and 25. The second example chooses all servers: the reliability sum is 456 and the minimum availability is 1.