ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Тренировочный турнир сезона «Зима — 2019» > задача:


J. Макс и муниципальная задача

Тренировочный турнир сезона «Зима — 2019»

Старт: 01.янв.2019 в 00:00:00
Финиш: 31.янв.2019 в 23:00:00
Осталось: 264:06:50
• Турнирная таблица

Задачи турнира

• B. Макс и приготовление супа
• C. Макс и простая задача
• D. Макс и сооружение города
• E. Никита и интервью
• F. Макс и поиск закусочных
• G. Макс и нестандартная спираль
• H. Макс и новогодние открытки
• I. Макс и распознавание фигур
• J. Макс и муниципальная задача
• K. СириусЛяндия и страсть к оливкам
• P1. Подбор отрезков ленты для од...
• P10. Бегущие огни в диагоналях
• P2. Подбор отрезков ленты для дв...
• P3. Подбор кусков ленты для ква...
• P4. Бегущий огонь слева направо в...
• P5. Бегущий огонь справа налево в...
• P6. Бегущие пары слева направо в...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 7000/7000/7000/7000 мс. Лимит памяти 262144/262144/262144/262144 Кб.

Макс и муниципальная задача
Макс и муниципальная задача
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды ученики показали Максу задачу, которая была первой — казалось бы, простейшей — из предложенных на одной школьной олимпиаде.

Героем этой задачи был фермер, владелец $$$N$$$ прямоугольных полей. Фермер однажды записал длину и ширину каждого из своих полей, но умудрился перепутать эти записи, поэтому теперь не помнит наверняка, к какому полю относится каждое из чисел, и которое из них — длина, в которое — ширина. Например, запись «$$$1~2~3~4~5~6$$$» может означать поля $$$1 \times 2$$$, $$$3 \times 4$$$ и $$$5 \times 6$$$, или поля $$$1 \times 3$$$, $$$5 \times 4$$$ и $$$6 \times 2$$$, или поля $$$3 \times 2$$$, $$$1 \times 5$$$ и $$$4 \times 6$$$, или другие возможные конфигурации.

На полях нужно засеять сельскохозяйственные культуры (на каждом поле — только одну). Для каждой культуры известна стоимость семян, которыми можно засеять площадь $$$1 \times 1$$$.

В задаче требовалось определить (внимание!) минимальную сумму денег, достаточную для покупки семян, которых хватило бы, чтобы полностью засеять хотя бы одну возможную конфигурацию полей... и при этом каждая культура была бы засеяна хотя бы на одном поле.

Макс попросил минутку на размышление...

$$$* * *$$$

...Спустя несколько часов Макс, Евгений, Даниил и Владимир склонились над условием задачи, как над картой военных действий. Стояла тревожная тишина.

— Увы, я, похоже, не знаю, как это решать, — решил признаться первым Макс. Остальные многозначительно переглянулись.

— Вот если бы фермер точно помнил, где длина, а где ширина... — сказал Евгений.

— Вот если бы культур было ровно столько же, сколько полей... — продолжил Даниил.

— Вот если бы ограничения были поменьше... — добавил Владимир.

— Тогда я сумею решить эту задачу! — подытожил Макс.

А вы сможете?

Входные данные

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 12$$$) — количество полей и культур.

Вторая строка содержит $$$N$$$ целых чисел $$$A_i$$$ ($$$1 \le A_i \le 100$$$) — длину каждого из полей.

Третья строка содержит $$$N$$$ целых чисел $$$B_i$$$ ($$$1 \le B_i \le 100$$$) — ширину каждого из полей.

Четвёртая строка содержит $$$N$$$ целых чисел $$$C_i$$$ ($$$1 \le C_i \le 100$$$) — стоимость семян каждой из культур, достаточных для засева площади $$$1 \times 1$$$.

Выходные данные

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

Примеры

Входные данные
3
1 2 3
2 3 3
2 1 2
Выходные данные
23
Входные данные
4
6 2 5 7
3 3 8 5
2 4 6 1
Выходные данные
210

Для отправки решений необходимо выполнить вход.

www.contester.ru