eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Агент

Агент

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

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

Приклад

Вхідні дані #1
2
3
6000 2 5500 3 5000 4
5
5005 1 5004 2 5003 3 5002 4 5001 5
Вихідні дані #1
5
7