8833번 - Manewry 다국어

Kapitan Pitt wraz ze swoją jednostką bierze udział w wojskowych manewrach. Najbliższe zadanie, które stoi przed jego zespołem, to pokonanie dwuczęściowego toru przeszkód.

Pierwsza przeszkoda to rwąca rzeka. Każdego żołnierza opisuje liczba A_i oznaczająca czas, jaki zajmie mu pokonanie rzeki. Druga przeszkoda to zasieki z drutu kolczastego. Analogicznie każdego żołnierza opisuje liczba B_i oznaczająca czas, jaki zajmie mu pokonanie zasiek.

Na początku wszyscy żołnierze znajdują się w punkcie startowym. Każdy z nich musi kolejno pokonać najpierw rzekę, a później zasieki. Ze względów bezpieczeństwa każdą przeszkodę może w danej chwili pokonywać tylko jeden żołnierz.

Kapitan Pitt doskonale zna swoich ludzi ( w szczególności zna liczby A_i , B_i ) i chce zaplanować kolejność w jakiej będą przechodzić tor, aby czas jego pokonywania był jak najkrótszy. Czas pokonywania toru mierzony jest od momentu w którym pierwszy żołnierz rozpocznie przeprawę przez rzekę do momentu w którym ostatni żołnierz skończy przedzierać się przez zasieki.

Możliwe oczywiście, że wielu żołnierzy jednocześnie będzie już za pierwszą przeszkodą, czekając na swoją kolej przejścia przez drugą przeszkodę.

W pierwsze linii znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10). Następnie podawane są opisy kolejnych zestawów.

W pierwszej linii zestawu znajduje się liczba naturalna N ( 1 <= 100000 ) oznaczająca liczbę żołnierzy w zespole Kapitana Pitta. W N kolejnych liniach znajdują się pary liczb A_i, B_i  ( 1 <= (A_i, B_i) <= 1000000 ) opisujących czasy przechodzenia przez przeszkody danego żołnierza.  

Dla każdego zestawu należy wypisać minimalny czas przejścia wszystkich żołnierzy przez tor.