You are trying to convince your friend to do your homework for you. Rather than bribing them like usual, you decide to persuade them using a new gadget you invented called the speech wheel.

The wheel is divided into ~N~ identical sectors, numbered from ~1~ to ~N~ in clockwise order. The ~i~th sector has a value of ~a_i~, representing its effectiveness on your friend.

Initially, each sector is occupied by a circular pie, with the pie in the ~i~th sector having a value of ~m_i~. At the end of a round, each pie moves to the next sector in clockwise order.

During each round, you will pick an unselected sector. If you pick sector ~i~, and pie ~j~ is currently occupying it, your score for that round is ~a_i \cdot m_j~. Your total score is the sum of your scores for each round.

A higher score means a greater probability to persuade your friend. Please find the maximum total score you can achieve if you continue until every sector has been picked.

For this problem, Python users are recommended to use PyPy.

Input Specification

The first line contains the integer ~N~ ~(1 \le N \le 19)~.

The next line contains the space-separated integers ~a_1, a_2, \dots, a_N~ ~(|a_i| \le 10^4)~.

The final line contains the space-separated integers ~m_1, m_2, \dots, m_N~ ~(1 \le m_i \le 10^4)~.

Output Specification

Output one line containing the maximum score you can achieve.

Sample Input

4
2 -1 1 -2
1 2 3 4

Sample Output

6

Explanation for Sample Output

One way to get a total score of ~6~ is the following:

Round ~1~: Pick sector ~3~ giving ~1 \cdot 3 = 3~

Round ~2~: Pick sector ~2~ giving ~-1 \cdot 1 = -1~

Round ~3~: Pick sector ~1~ giving ~2 \cdot 3 = 6~

Round ~4~: Pick sector ~4~ giving ~-2 \cdot 1 = -2~