Новогодние подарки

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

Список задач