Welcome to the final game.

Only 2 contestents remain. You and your worst enemy: HenryZ. Together, you play a game involving a 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 ~i~ 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.

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, ..., a_N~ ~(-10^4 \le a_i \le 10^4)~.

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

Output Specification

Output one line containing the maximum score you can achieve.

Subtasks

Subtask 1 [20%]

~1 \le N \le 3~

Subtask 2 [80%]

~1 \le N \le 19~

Sample Input 1

3
2 -1 1
1 2 3

Sample Output 1

6

Sample Explanation 1

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 2 = 4~