Pasażerowie autokarów turystycznych, przewożących wycieczki transkontynentalną autostradą, spędzają w drodze wiele dni, zatem opłaty za noclegi stanowią poważną część kosztów podróży. Ze względu na bezpieczeństwo jazdy i wygodę pasażerów każdy autokar jedzie tylko w ciągu dnia i nie może przejechać więcej niż 800 km dziennie. Noce na trasie (poza jej początkiem i końcem) pasażerowie i kierowca spędzają w hotelach. Dotychczas planowano przejazdy tak, by liczba noclegów na trasie była jak najmniejsza. Dążąc do obniżki kosztów, przedsiębiorstwo przewozowe zdecydowało zbadać, czy opłaci się układanie planów podróży tak, by suma opłat za noclegi była możliwie najniższa, nawet gdyby to miało przedłużyć podróż. W tych obliczeniach można korzystać z ofert hoteli położonych przy autostradzie. W każdej ofercie jest podana odległość hotelu od początku trasy i cena jednego noclegu jednej osoby. Podróż jest tylko w jedną stronę. Trasa nie ma rozgałęzień. Przez każdy punkt trasy autokar przejeżdża jeden raz. Nigdzie na trasie nie ma dwóch hoteli w jednym punkcie, więc dla zidentyfikowania hotelu wystarczy podać jego odległość od początku trasy. Nie planuje się noclegu na początku ani na końcu trasy. Liczba osób w autobusie nie zmienia się i w każdym hotelu wszyscy (łącznie z kierowcą) płacą za nocleg jednakowo - zgodnie z ofertą. Pojemność hoteli jest na tyle duża, że nie istnieje problem braku miejsc. Zawsze można liczyć na to, że w dowolnej chwili w każdym hotelu będzie wystarczająco dużo wolnych miejsc, by przenocować wszystkich pasażerów autobusu. Na każdym odcinku trasy o długości 800 km jest przynajmniej jeden hotel, co oznacza, że przejechanie trasy z zachowaniem podanych wyżej warunków jest możliwe.

Zadanie

• wczytuje z pliku tekstowego TAN.IN dane: długość trasy, liczbę hoteli oraz oferty hoteli;
• znajduje dwa plany podróży:
  • najtańszej, tzn. takiej, żeby suma opłat za hotele była najmniejsza, a jeśli takich rozwiązań jest wiele, wybiera jedno z najmniejszą liczbą noclegów,
  • najszybszej, tzn. takiej, żeby liczba noclegów była najmniejsza, a jeśli takich rozwiązań jest wiele, wybiera jedno z najmniejszą sumą opłat za noclegi;
• zapisuje wyniki, tj. dwa plany podróży - najtańszej i najszybszej, w pliku tekstowym TAN.OUT.

Wejście

W pierwszym wierszu pliku tekstowego TAN.IN są zapisane dwie liczby całkowite dodatnie, oddzielone pojedynczym odstępem: długość trasy d w kilometrach oraz liczba hoteli h, gdzie dŁ16000 i hŁ1000. W kolejnych h wierszach są zapisane oferty hoteli - każda oferta w osobnym wierszu. Są one uporządkowane według rosnącej odległości hoteli od początku trasy. Każda oferta jest zapisana w postaci dwóch liczb całkowitych dodatnich oddzielonych pojedynczym odstępem, pierwsza liczba - to odległość hotelu od początku trasy w kilometrach, a druga - to cena jednego noclegu w tym hotelu nie większa niż 1000.

Wyjście

W pierwszym wierszu pliku tekstowego TAN.OUT należy zapisać plan podróży najtańszej - odległości kolejnych miejsc noclegu od początku trasy. W drugim wierszu należy - w taki sam sposób - zapisać plan podróży najszybszej. Liczby w wierszu powinny być pooddzielane pojedynczym odstępem.

Przykład

Dla pliku TAN.IN

2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40

400 1200
400 1200

Twój program powinien szukać pliku TAN.IN w katalogu bieżącym i tworzyć plik TAN.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę TAN.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku TAN.EXE