Agent

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

Задание Бонда состоит в том, чтобы агенты нашли друг другу напарников таким образом, чтобы у каждого агента был хотя бы один напарник (всего у агента может быть 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.