Новорічні подарунки

prb26 Діду Морозу і Снігурочці потрібно доставити n подарунків дітям.

Знаючи час t₁ пакування кожного подарунку Снігурочкою та час його доставки Дідом Морозом t₂, знайти найменший час, за який вони зможуть виконати всі замовлення. В свій мішок Дід Мороз може вкласти лише один подарунок.

Технічні умови

Вхідні дані

У першому рядку єдине число n (1 ≤ n ≤ 300) - кількість подарунків. У наступних двох рядках через пропуск по n чисел, відповідно: у другому рядку - час пакування кожного подарунку Снігуронькою, у третьому - час його доставки Дідом Морозом. Відомо, що 0 < t₁, t₂ ≤ 1000.

Вихідні дані

Найменший час доставки усіх подарунків.

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 9.09091
Складність: 49% 69/135
Класифікація: Жадний алгоритм

Приклад

Приклад вхідних даних

5
4   4   30    6    2
5   1    4    30   3

Приклад вихідних даних

← Paint3D

Список задач