e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Məsələlər

Агент

Агент

Агент Джеймс Бонд пошел на пенсию, но неугомонный характер требовал новых впечатлений. Поэтому Джеймс Бонд с удовольствием согласился провести мастер-класс в некоторых группах школы "Молодого агента". Тема одного из занятий – работа агента с напарником. В таком опасном деле, как разведка, важно иметь очень надёжного напарника, поэтому напарниками могут стать только агенты, которые максимально близки по возрасту (т.е. два агента не могут стать напарниками, если в группе существует третий агент, который старше одного и младше другого).

Задание Бонда состоит в том, чтобы агенты нашли друг другу напарников таким образом, чтобы у каждого агента был хотя бы один напарник (всего у агента может быть 2 напарника – один младше, и один старше него, но эти двое не считаются напарниками между собой). Очевидно, что группа из 4 и более агентов может поделиться несколькими способами.

После нескольких занятий Бонд узнал способности групп, обучающихся в школе "Молодого агента", и оценил риск раскрытия каждого агента в отдельности. Но специфика работы с напарником такова, что в паре риску подвергается только старший из двух агентов, поэтому группу надо распределить так, чтобы суммарный риск был минимален.

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

В первой строке входного файла находится одно целое число M (1 <= M <= 13) – количество групп, в которых проводит мастер-класс Джеймс Бонд. Далее последовательно идёт M описаний группы. Описание каждой группы состоит из двух строк. В первой строке находится одно целое число N – количество агентов в группе (2 <= N <= 10000). Во второй строке находятся N пар целых положительных чисел, разделённых пробелом. Первое число в паре – это возраст агента (в днях) из диапазона [5000, 16000], второе – риск раскрытия агента, число в диапазоне [1, 1000]. Известно, что в любой группе все агенты разного возраста.

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

Для каждой группы в отдельной строке выведите число – минимальное значение суммарного риска раскрытия группы.

Комментарии к примеру: в первой группе выбирать себе напарников не приходится – вариант разделения всего один: пара 6000-5500 (риск 2) и пара 5500-5000 (риск 3).

Во второй группе агенты 5005 и 5001, как крайние по возрасту, без вариантов получают в качестве напарников 5004 и 5002 соответственно. А вот оставшийся без напарника агент 5003 может выбрать себе 5004 либо 5002. В паре с 5004 риск меньше (2 против 3), поэтому оптимальное разделение имеет суммарный риск 1 + 2 + 4 = 7.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
2
3
6000 2 5500 3 5000 4
5
5005 1 5004 2 5003 3 5002 4 5001 5
Çıxış verilənləri #1
5
7