e-olymp
Задачі

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

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

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

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

prb26

Вхідні дані

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

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5
4 4 30 6 2
5 1 4 30 3

Вихідні дані #1
47