Problem B - Number Box
box.in
Output file:
box.out
A number box consists of two rows and N columns. Each square of the box can contain a non-zero integer from the range from -10 to 10. The figure below shows a number box with N = 7.
The value of a number box is defined as the sum of multiplications between pairs of numbers in the same column (the value of an empty square is 0). Thus, the value of the above box is -6.
It is allowed to shift the numbers to the left or right, maintaining the order or the numbers within each row. For example, shifting the numbers 5 and -1 in the first row to the left by one, the number -3 in the second row to the left by one and the numbers 2 and 4 in the second row to the right by one square, we reach the state shown below and the value of the box becomes 36.
Write a program to find the maximal possible value of a number box.
Input
The first line of the input file contains an integer N (1 ≤ N ≤ 400), the number of columns of the box. The following two lines contain the initial state of the box, with the empty squares denoted by 0 and the non-empty squares denoted by the values they contain.
Output
The first and only line of the output file must contain the maximal possible value of the box that can be achieved by shifting the numbers while maintaining the order of the numbers within each row.
Sample Input
7 -3 -1 -2 0 5 -1 0 0 -3 2 4 0 5 -2
Sample Output
36