Республиканская олимпиада по информатике 2019 года за 9 класс | Казахстанские олимпиады

Задача D. Выбор Айбара

У Айбара есть два массива $A$ и $B$, что размер каждого равен $n$. Для каждого $i$, что $(1 <= i <= n)$, Айбар должен выбрать либо $A_i$, либо $B_i$. Он хочет максимизировать произведение суммы выбранных $A_i$ и суммы выбранных $B_j$. Помогите Айбару найти максимальное значение.

Формат входного файла

Первая строка содержит одно целое число $n$ $(2 <= n <= 1000)$.

Вторая строка содержит $n$ целых чисел $A_1, A_2, A_3,...A_n$ $(1 <= A_i <= 10^9)$.

Третья строка содержит $n$ целых чисел $B_1, B_2, B_3,...B_n$ $(1 <= B_i <= 10^9)$.

Формат выходного файла

Выведите одно целое число -- ответ на задачу.

Примеры

Вход

5
1 4 3 2 5
5 2 2 4 1

Выход

108

Вход

2
5 7
3 5

Выход

25

Вход

7
1 1 1 1 1 1 1
1 1 1 1 1 1 1

Выход

12