H. Hard Array Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an array problem.

Given two arrays of $$$N$$$ numbers with values $$$A_1, \dots, A_N$$$ and $$$B_1, \dots, B_N$$$. Let $$$A_{L, R}$$$ be the sum of elements in the subarray of $$$A$$$ from index $$$L$$$ to $$$R$$$ inclusive. Let $$$B_{L, R}$$$ be defined similarly.

Minimise $$$A_{L, R}^2 + B_{L, R}^2$$$ across all $$$1\leq L \leq R \leq N$$$.

Input

The first line contains a single integer, $$$N$$$, the length of both arrays.

The second line contains $$$N$$$ space-separated integers, $$$A_1, A_2, \dots, A_N$$$.

The second line contains $$$N$$$ space-separated integers, $$$B_1, B_2, \dots, B_N$$$.

Output

Output a single integer, the minimised sum.

Scoring

$$$1 \leq N \leq 5 \times 10^5$$$

$$$-10^9 \leq A_i, B_i \leq 10^9$$$

Examples
Input
3
4 -1 -1
-1 -1 4
Output
2
Input
2
4 -4
1 1
Output
4