eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 256 MiB

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

Нехай є 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

Input example #1
3
5 4 6
1 2 3
Output example #1
24
Input example #2
5
2 3 4 4 5
5 4 4 3 1
Output example #2
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\% балів.

Author Kostya Denisov