eolymp
bolt
Try our new interface for solving problems
Problems

ГАС Очередь

ГАС Очередь

Time limit 2 seconds
Memory limit 256 MiB

За последние несколько лет электронные очереди прочно вошли в повседневную жизнь. Во многих государственных учреждениях можно встретить терминал, печатающий бумажку с номером, и, не задавая привычный вопрос "Кто последний?", посетители с помощью электронного табло узнают, сколько еще им ждать и когда наступит их очередь.

Однако, пока такие системы далеки от совершенства. Например, вызывает вопросы стандартный принцип любой очереди: "Первым обслуживается тот, кто первым пришел". При разработке инновационной ГАС "Очередь" решено было сделать ее такой, что выполнение этого принципа не требуется. Вместо этого, новая система призвана минимизировать количество негатива, приходящегося на чиновника, на прием к которому стоят люди в очереди.

Известно, что у каждого человека есть такой критерий, как раздражительность. Если этот параметр равен w, то через t часов ожидания в очереди этот человек обрушит на голову чиновника ровно wt единиц злобы и ругани. Так, если посетителя начнут обслуживать сразу же после его прихода, то чиновник не пострадает, а если посетитель пришел в начале третьего часа, а его обслуживание началось только в начале пятого — количество гнева будет равно 2w.

Также известно, что на обслуживание каждого посетителя уходит ровно час, а каждый посетитель приходит в начале какого-либо часа. Ваша задача заключается в том, чтобы по данным вам показателям раздражительности и временам прихода посетителей определить, сколько негатива достанется чиновнику при оптимальном порядке обслуживания клиентов.

Input data

В первой строке задано одно целое число t — количество случаев, которые вам предстоит обработать. Далее следуют t описаний самих случаев.

Описание каждого случая состоит из: числа n в первой строке — количества посетителей, и n описаний самих посетителей. Для каждого посетителя в отдельной строке указаны два целых числа r_i и w_i (1r_i, w_i10^6) — номер часа, в начале которого посетитель пришел, и его коэффициент раздражительности, соответственно.

Суммарное количество посетителей во всех случаях одного теста не превосходит 10^5.

Output data

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

Examples

Input example #1
2
3
1 3
1 3
1 3
3
1 3
2 5
1 4
Output example #1
9
6