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

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 256 мегабайтів

Нещодавно Козак Вус відвідав лекцію з математики. Після лекції він придумав наступну задачу.

Нехай є $2$ масиви $a$ та $b$ з $n$ елементів. Тоді $f (i, j) = a_{i} \cdot b_{j} + b_{i} \cdot a_{j}$ , де $1 \leq i < j \leq n$ .

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

Козак Вус вже стомився розв'язувати цю задачу, тому він просить Вас допомогти йому.

Вхідні дані

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

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

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

Вихідні дані

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

Приклади

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Примітка

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

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

Оцінювання

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

Відправки 5