Cyclic Shift Dot Product

Time limit1sMemory limit512 MB

Summary

Rotate two length-N sequences by any amounts to maximize their dot product, and print that maximum.

Level: Hard8 of 10
Topics: Combinatorics, Math, Sorting
Solved: No attempts yet

Problem

There are two sequences X and Y, each containing N numbers. One cyclic shift removes the last element of a sequence and inserts it at the front. For example, one cyclic shift changes {1, 2, 3} into {3, 1, 2}, and another shift changes it into {2, 3, 1}.

You may apply zero or more cyclic shifts to X, and independently zero or more cyclic shifts to Y. After all shifts, compute the score S as follows.

S = X[0] * Y[0] + X[1] * Y[1] + ... + X[N-1] * Y[N-1]

Find the maximum possible value of S.

Input

The first line contains the integer N.

The second line contains the N numbers in X. The third line contains the N numbers in Y.

N is a positive integer not greater than 60,000. Every number in X and Y is an integer from 0 to 99, inclusive.

Output

Print the maximum possible value of S.

Examples3

Example 1
Input
```
4
1 2 3 4
6 7 8 5
```
Expected output
```
70
```
Example 2
Input
```
5
1 1 1 1 1
1 1 1 1 1
```
Expected output
```
5
```

Example 3

Input

10
23 4 95 20 17 94 63 44 13 96
87 54 13 18 61 24 17 94 53 2

Expected output