Number Box

A number box has two rows, an upper row and a lower row, and N columns. It has 2N cells in total. Each cell may either be empty or contain one nonzero integer tile whose value is between -10 and 10.

The following table shows one possible box when N = 7; blank cells are empty.

The value of a number box is the sum, over all columns, of the product of the upper and lower entries in that column. An empty cell is treated as 0. For the box above, the value is (-3)×0 + (-1)×(-3) + (-2)×2 + 0×4 + 5×0 + (-1)×5 + 0×(-2) = -6.

You may move the tiles in each row left or right into empty cells, but the relative order of the tiles in the same row must remain unchanged. Tiles cannot pass through each other or swap positions. For example, moving the upper tiles 5 and -1 one column to the right, moving the lower tile -3 one column to the left, and moving the lower tiles 2 and 4 one column to the right can produce this box:

Its value is 9 + 25 + 2 = 36.

Given the initial number box, compute the maximum possible value obtainable by moving tiles horizontally while preserving the order of the tiles in each row.

The first line contains an integer N (1 <= N <= 400), the number of columns.

Each of the next two lines contains N integers describing one row of the initial box: first the upper row, then the lower row. A 0 means the cell is empty. Every tile value is a nonzero integer between -10 and 10, inclusive.

Print the maximum possible value of the number box after moving the tiles.