Агент Джеймс Бонд пошел на пенсию, но неугомонный характер требовал новых впечатлений. Поэтому Джеймс Бонд с удовольствием согласился провести мастер-класс в некоторых группах школы "Молодого агента". Тема одного из занятий -- работа агента с напарником. В таком опасном деле, как разведка, важно иметь очень надёжного напарника, поэтому напарниками могут стать только агенты, которые максимально близки по возрасту (т.е. два агента не могут стать напарниками, если в группе существует третий агент, который старше одного и младше другого). Задание Бонда состоит в том, чтобы агенты нашли друг другу напарников таким образом, чтобы у каждого агента был хотя бы один напарник (всего у агента может быть \textbf{2} напарника -- один младше, и один старше него, но эти двое не считаются напарниками между собой). Очевидно, что группа из \textbf{4} и более агентов может поделиться несколькими способами. После нескольких занятий Бонд узнал способности групп, обучающихся в школе "Молодого агента", и оценил риск раскрытия каждого агента в отдельности. Но специфика работы с напарником такова, что в паре риску подвергается только старший из двух агентов, поэтому группу надо распределить так, чтобы суммарный риск был минимален. \InputFile В первой строке входного файла находится одно целое число \textbf{M} (\textbf{1} <= \textbf{M} <= \textbf{13}) -- количество групп, в которых проводит мастер-класс Джеймс Бонд. Далее последовательно идёт \textbf{M} описаний группы. Описание каждой группы состоит из двух строк. В первой строке находится одно целое число \textbf{N} -- количество агентов в группе (\textbf{2} <= \textbf{N} <= \textbf{10000}). Во второй строке находятся \textbf{N} пар целых положительных чисел, разделённых пробелом. Первое число в паре -- это возраст агента (в днях) из диапазона \[\textbf{5000}, \textbf{16000}\], второе -- риск раскрытия агента, число в диапазоне \[\textbf{1}, \textbf{1000}\]. Известно, что в любой группе все агенты разного возраста. \OutputFile Для каждой группы в отдельной строке выведите число -- минимальное значение суммарного риска раскрытия группы. \textbf{Комментарии к примеру:} в первой группе выбирать себе напарников не приходится -- вариант разделения всего один: пара \textbf{6000}-\textbf{5500} (риск \textbf{2}) и пара \textbf{5500}-\textbf{5000} (риск 3). Во второй группе агенты \textbf{5005} и \textbf{5001}, как крайние по возрасту, без вариантов получают в качестве напарников \textbf{5004} и \textbf{5002} соответственно. А вот оставшийся без напарника агент \textbf{5003} может выбрать себе \textbf{5004} либо \textbf{5002}. В паре с \textbf{5004} риск меньше (\textbf{2} против \textbf{3}), поэтому оптимальное разделение имеет суммарный риск \textbf{1} + \textbf{2} + \textbf{4} = \textbf{7}.