Магічна функція

Input

Перший рядок містить одне ціле число $n$ ( $2 \leq n \leq 1 0^{5}$ 2 \le n \le 10^5) — довжина масивів $a$ та $b$ .

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $1 \leq a_{i} \leq 1 0^{6}$ 1 \le a_i \le 10^6) — масив $a$ .

Третій рядок містить $n$ цілих чисел $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \dots, b_n ( $0 \leq b_{i} \leq 1 0^{3}$ 0 \le b_i \le 10^3) — масив $b$ .

Output

Виведіть єдине число — максимальне значення функції $f (i, j)$ f(i, j), де $1 \leq i < j \leq n$ 1 \le i < j \le n.

Examples

Example 1

Loading

Example 2

Loading

Note

У першому прикладі можна вибрати $i = 2$ i=2 та $j = 3$ j=3, тоді $f (2, 3) = a_{2} \cdot b_{3} + b_{2} \cdot a_{3} = 4 \cdot 3 + 2 \cdot 6 =$ f(2, 3)=a_2 \cdot b_3 + b_2 \cdot a_3 = 4 \cdot 3 + 2 \cdot 6 = $= 12 + 12 = 24$ =12 + 12 = 24.

У другому прикладі можна вибрати $i = 3$ i=3 та $j = 4$ j=4, тоді $f (3, 4) = a_{3} \cdot b_{4} + b_{3} \cdot a_{4} = 4 \cdot 3 + 4 \cdot 4 =$ f(3, 4)=a_3 \cdot b_4 + b_3 \cdot a_4 = 4 \cdot 3 + 4 \cdot 4 = $= 12 + 16 = 28$ =12 + 16 = 28.

Scoring

Гарантується, що рішення, які працюватимуть правильно при $n \leq 1000$ n \leq 1000, отримають принаймні $50%$ балів.