POLSKI SPOJ

Firma "FRAKTAX" ma do wykonania bardzo ważne zadanie i musi korzystać z usług superkomputera. Superkomputer można rezerwować jedynie na cały dzień i nikt inny w tym czasie nie ma do niego dostępu. Wiadomo także, że ta super maszyna w ciągu jednego dnia poradzi sobie z każdym zadaniem. Bywa często tak, że pracownicy firmy, muszą ustawiać się w kolejce rezerwując kolejne dni. Okazuje się jednak, że w skutek złego planowania, firma nie realizuje swoich zleceń w terminowym czasie, za co ponosi kary pieniężne. Znając terminy na wykonanie zadań oraz kary za ich przekroczenie, określ, jaką najmniejszą karę może zapłacić firma.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zestawów testowych (nie więcej niż 100).

Specyfikacja każdego zestawu testowego.

W pierwszym wierszu jedna liczba n określająca liczbę zadań (n < 100001).

Każde zadanie składa się z terminu p na zadanie oraz kary k za przekroczenie tego terminu (p ∈ [1..n], k ∈ [1..100000]).

Wyjście

Dla każdego zestawu minimalna kara, jaką firma FRAKRAX może zapłacić za niedotrzymanie terminów.

Przykład

Wejście:
1
7
2 60
4 50
4 70
6 10
4 20
1 30
3 40

Wyjście:
50