Firma kapitana Mambeksa zajmuje się transportem samochodowym. Ostatnio kapitan postanowił zredukować koszty związane z noclegami. Ciężarówki przewożą towary jadąc przez autostrady. Kierowcy ciężarówek nocują w motelach. Motele pobierają za nocleg opłatę w wysokości od 1 do 100$. Przepisy na planecie kapitana stanowią że kierowca ciężarówki może przejechać w jeden dzień maksymalnie 200 km. Napisz program który na podstawie cen noclegów i położenia moteli obliczy minimalny koszt noclegów pozwalający na przejechanie autostrady zgodnie z przepisami.
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych n (0 ≤ n i n ≤ 20). W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. W pierwszym wierszu zestawu danych są zapisane dwie liczby: długość autostrady k, (k > 0 i k < 100000) oraz ilość moteli m (1 ≤ m i m ≤ 10000). W kolejnych m wierszach zapisana jest odległość motelu od początku autostrady d, (d > 0 i d < k) oraz koszt noclegu w motelu c, (c > 0 i c ≤ 100).
Dla każdego zestawu danych wejściowych program ma wypisać jeden wiersz zawierający minimalną sumę cen za noclegi wymaganą do przejechania całej długości autostrady zgodnie z przepisami. W przypadku gdy nie jest możliwe przejechanie przez autostradę zgodnie z przepisami program powinien wypisać wiersz zawierający słowo Impossible.
1
500 4
100 50
150 1
300 40
409 44
41