Kapitan Mamlaków zacięty wróg Kapitana Mambeksa kupił najnowszy model myśliwskiego
statku kosmicznego. Postanowił się szybko wzbogacić jako najemnik, każdy kto
zapłaci 5 galonów melanżu za dzień może wynająć Kapitana Mamlaków do
swoich niecnych celów. Posiada on niestety tylko jeden statek wiec może równocześnie
wykonywać tyko jedno zlecenie, by nie tracić klientów realizuje je zawsze w
całości, może jednak w dniu końca zlecenia rozpocząć już kolejne
zlecenie. Kapitan otrzymał już wiele różnych ofert na przyszłe
100 lat i teraz chce się dowiedzieć ile maksymalnie jest w stanie zarobić
melanżu. Twoim zadaniem jako jego asystenta jest napisać program który
wyliczy ile maksymalnie galonów melanżu Kapitan zarobi.
Dane wejściowe:
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych. W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. Każdy zestaw składa się z :
N – liczba zamówień ( 0 < N <= 10000 )
N linii zawierających pojedyncze zamówienia:
TP TK gdzie 0 <= TP < 10000 i TP < TK <= 10000 ( TP - czas początku,
TK - czas końca zamówienia )
Dane wyjściowe
Dla każdego zestawu danych wejściowych program ma wypisać w kolejnych
wierszach:
Maksymalną liczbę galonów melanżu która Kapitan
zarobi.
Przykładowe dane wejściowe:
1
3
0 1
2 3
0 3
Przykładowe dane wyjściowe:
15