Tích chập

Alice định nghĩa tích chập của hai dãy số cùng độ dài \(u_{1}, u_{2}, \ldots, u_{n}\) và \(v_{1}, v_{2}, \ldots, v_{n}\) là giá trị \(\sum_{i = 1}^{n} u_{i} \times v_{i} = u_{1} \times v_{1} + u_{2} \times v_{2} + \cdots + u_{n} \times v_{n}\). Với hai dãy số \(a_{1}, a_{2}, \ldots, a_{n}\) và \(b_{1}, b_{2}, \ldots, b_{n}\) cùng độ dài \(n\), Alice muốn tìm hai đoạn trên hai dãy thỏa mãn:

• Mỗi dãy chọn một đoạn khác rỗng (gồm các phần tử liên tiếp).
• Hai đoạn có số lượng phần tử bằng nhau.
• Tích chập của hai dãy số là hai đoạn đã chọn là lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) \((n \leq 5000)\).

• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((|a_{i}| \leq 10^{6})\) mô tả dãy số thứ nhất.

• Dòng thứ ba chứa n số nguyên \(b_{1}, b_{2}, \ldots, b_{n}\) \((|b_{i}| \leq 10^{6})\) mô tả dãy số thứ hai.

Output

• In ra một số nguyên duy nhất là tích chập của hai đoạn tìm được.

Example

3
1 2 3
-1 -2 -3

-1

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 50\).

• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 500\).

• Subtask \(3\) (\(20\%\) số điểm): không có rằng buộc gì thêm.