Магічна функція
Магічна функція
Нещодавно Козак Вус відвідав лекцію з математики. Після лекції він придумав наступну задачу.
Нехай є 2 масиви a та b з n елементів. Тоді f(i, j) = a_i \cdot b_j + b_i \cdot a_j, де 1 \le i < j \le n.
Козака Вуса дуже зацікавило максимальне значення функції f(i, j), де 1 \le i < j \le n.
Козак Вус вже стомився розв'язувати цю задачу, тому він просить Вас допомогти йому.
Input data
Перший рядок містить одне ціле число n (2 \le n \le 10^5) — довжина масивів a та b.
Другий рядок містить n цілих чисел a_1, a_2, \dots, a_n (1 \le a_i \le 10^6) — масив a.
Третій рядок містить n цілих чисел b_1, b_2, \dots, b_n (0 \le b_i \le 10^3) — масив b.
Output data
Виведіть єдине число — максимальне значення функції f(i, j), де 1 \le i < j \le n.
Examples
3 5 4 6 1 2 3
24
5 2 3 4 4 5 5 4 4 3 1
28
Note
У першому прикладі можна вибрати 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.
Scoring
Гарантується, що рішення, які працюватимуть правильно при n \leq 1000, отримають принаймні 50\% балів.