|
Агент
(Время: 1 сек. Память: 16 Мб Сложность: 34%)
Агент Джеймс Бонд пошел на пенсию, но неугомонный характер требовал новых впечатлений. Поэтому Джеймс Бонд с удовольствием согласился провести мастер-класс в некоторых группах школы «Молодого агента». Тема одного из занятий – работа агента с напарником. В таком опасном деле, как разведка, важно иметь очень надёжного напарника, поэтому напарниками могут стать только агенты, которые максимально близки по возрасту (т.е. два агента не могут стать напарниками, если в группе существует третий агент, который старше одного и младше другого).
Задание Бонда состоит в том, чтобы агенты нашли друг другу напарников таким образом, чтобы у каждого агента был хотя бы один напарник (всего у агента может быть 2 напарника – один младше, и один старше него, но эти двое не считаются напарниками между собой). Очевидно, что группа из 4 и более агентов может поделиться несколькими способами.
После нескольких занятий Бонд узнал способности групп, обучающихся в школе «Молодого агента», и оценил риск раскрытия каждого агента в отдельности. Но специфика работы с напарником такова, что в паре риску подвергается только старший из двух агентов, поэтому группу надо распределить так, чтобы суммарный риск был минимален.
Входные данные
В первой строке входного файла INPUT.TXT находится одно целое число N – количество агентов в группе (2 ≤ N ≤ 10000). Во второй строке находятся N пар целых положительных чисел, разделенных пробелом. Первое число в паре – это возраст агента (в днях) из диапазона [5000, 16000], второе – риск раскрытия агента, число в диапазоне [1, 1000]. Известно, что в любой группе все агенты разного возраста.
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – минимальное значение суммарного риска раскрытия группы.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 6000 2 5500 3 5000 4 | 5 |
2 | 5 5005 1 5004 2 5003 3 5002 4 5001 5 | 7 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |