Торгівельний центр
Торгівельний центр
У країні Олімпії вирішили побудувати великий торговельний центр. Задля цього було виділено квадратну ділянку NxNметрів. Існують певні обмеження щодо висоти будівлі. А саме: якщо розбити схему ділянки на вертикальні та горизонтальні смуги шириною 1 метр, то будівля в межах однієї смуги буде мати певне своє обмеження на висоту. Архітектори бажають побудувати торговельний центр у формі прямокутного паралелепіпеда.
Завдання
Напишіть програму, що за даними про розмір ділянки та обмеження по висоті по кожній зі смуг знайде максимальний об'єм будівлі у формі прямокутного паралелепіпеда, яку можна збудувати на цій ділянці.
Вхідні дані
Вхідний файл складається з трьох рядків. У першому рядку міститься натуральне числоN (2 ≤ N ≤ 5х10^4) — розмір ділянки. Другий рядок містить N невід’ємних цілих чисел, кожне з яких не перевищує 10^5, — обмеження висоти по вертикальних смугах. Третій рядок також містить N невід’ємних цілих, кожне з яких не перевищує 10^5, — обмеження висоти по горизонтальних смугах.
Вихідні дані
Вихідний файл повинен містити єдине число — максимальний об’єм будівлі торговельного центру, яку можна збудувати на описаній ділянці. Вхідні дані гарантують можливість збудувати на ділянці будівлю ненульового об’єму.
Приклад
10 33610 86494 45587 32272 84247 39686 95196 49914 62036 49552 50000 50001 50002 50003 50004 50005 50004 50003 50002 50001
3227200
Оцінювання
Набір тестів складається з 5 блоків, для яких додатково виконуються такі умови:
10 балів: 1 ≤ N ≤ 10
10 балів: 10 < N ≤ 30
10 балів: 30 < N ≤ 70
30 балів: 70 < N ≤ 1000
40 балів: 1000 < N ≤ 5х10^4