Агент#403

Агент

1 секунда

64 мегабайти

Легка

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

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

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

Вхідні дані

У першому рядку вхідного файлу знаходиться одне ціле число $M$ ( $1 \leq M \leq 13$ 1 \leq M \leq 13) – кількість груп, у яких проводить майстер-клас Джеймс Бонд. Далі послідовно йде $M$ описів груп. Опис кожної групи складається з двох рядків. У першому рядку знаходиться одне ціле число $N$ – кількість агентів у групі ( $2 \leq N \leq 10000$ 2 \leq N \leq 10000). У другому рядку знаходяться $N$ пар цілих додатних чисел, відокремлених пропуском. Перше число у парі – це вік агента (у днях) з діапазону $5000$ до $16000$ , друге – ризик викриття агента, число у діапазоні $1$ до $1000$ . Відомо, що в будь-якій групі всі агенти різного віку.

Вихідні дані

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

Приклади

Приклад 1

Примітка

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

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