1750. Агент

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

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

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

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

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

2
3
6000 2 5500 3 5000 4
5
5005 1 5004 2 5003 3 5002 4 5001 5

5
7

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

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