eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Торгівельний центр

Торгівельний центр

Ліміт часу 0.2 секунд
Ліміт використання пам'яті 256 MiB

У країні Олімпії вирішили побудувати великий торговельний центр. Задля цього було виділено квадратну ділянку NxNметрів. Існують певні обмеження щодо висоти будівлі. А саме: якщо розбити схему ділянки на вертикальні та горизонтальні смуги шириною 1 метр, то будівля в межах однієї смуги буде мати певне своє обмеження на висоту. Архітектори бажають побудувати торговельний центр у формі прямокутного паралелепіпеда.

Завдання

Напишіть програму, що за даними про розмір ділянки та обмеження по висоті по кожній зі смуг знайде максимальний об'єм будівлі у формі прямокутного паралелепіпеда, яку можна збудувати на цій ділянці.

Вхідні дані

Вхідний файл складається з трьох рядків. У першому рядку міститься натуральне числоN (2 ≤ N ≤ 5х10^4) — розмір ділянки. Другий рядок містить N невід’ємних цілих чисел, кожне з яких не перевищує 10^5, — обмеження висоти по вертикальних смугах. Третій рядок також містить N невід’ємних цілих, кожне з яких не перевищує 10^5, — обмеження висоти по горизонтальних смугах.

Вихідні дані

Вихідний файл повинен містити єдине число — максимальний об’єм будівлі торговельного центру, яку можна збудувати на описаній ділянці. Вхідні дані гарантують можливість збудувати на ділянці будівлю ненульового об’єму.

Приклад

Вхідні дані #1
10
33610 86494 45587 32272 84247 39686 95196 49914 62036 49552
50000 50001 50002 50003 50004 50005 50004 50003 50002 50001
Вихідні дані #1
3227200

Оцінювання

Набір тестів складається з 5 блоків, для яких додатково виконуються такі умови:

  1. 10 балів: 1 ≤ N ≤ 10

  2. 10 балів: 10 < N ≤ 30

  3. 10 балів: 30 < N ≤ 70

  4. 30 балів: 70 < N ≤ 1000

  5. 40 балів: 1000 < N ≤ 5х10^4

Автор Роман Єдемський
Джерело XXVII Всеукраїнська учнівська олімпіада з інформатики (2014) Дніпропетровськ