Przeprawa

Limit pamięci: 32 MB

Drużyna Bajtołazów wybrała się na wycieczkę w Bajtogóry. Niestety spowodowali lawinę i muszą przed nią uciekać. Na ich drodze znajduje się przepaść i stary most linowy. Muszą jak najszybciej przeprawić się przez most na drugą stronę. Bajtołazi są bardzo zgrani i postanowili, że albo wszyscy się uratują, albo nikt.

Most jest stary i zniszczony, więc nie wytrzyma zbyt dużego obciążenia. Łączna waga Bajtołazów znajdujących się równocześnie na moście nie może być większa od wytrzymałości mostu. Ponadto jest to most linowy. Bajtołazi muszą więc przechodzić przez niego grupami. Kolejna grupa może wejść na most dopiero wtedy, gdy poprzednia go opuści.

Dla każdego Bajtołaza wiadomo, ile czasu zajmie mu przeprawa przez most. Czas przeprawy przez most grupy Bajtołazów jest równy czasowi potrzebnemu na przeprawę przez most najwolniejszego członka grupy. Łączny czas przeprawy wszystkich Bajtołazów to suma czasów przeprawy wszystkich grup. Oczywiście zależy on od tego, jak się podzielą na grupy przechodząc przez most.

Pomóż Bajtołazom uratować się! Oblicz, jaki jest minimalny czas przeprawy przez most wszystkich Bajtołazów.

Zadanie

Napisz program, który:

• wczyta z wejścia opis mostu oraz Bajtołazów,
• wyznaczy najkrótszy czas przeprawy wszystkich Bajtołazów przez most,
• wypisze wyznaczony czas na wyjście.

Wejście

Pierwsza linia standardowego wejścia zawiera dwie liczby całkowite oddzielone pojedynczym odstępem: - określającą maksymalne dopuszczalne obciążenie mostu () oraz - równą liczbie Bajtołazów (). W kolejnych wierszach znajdują się po dwie liczby całkowite oddzielone pojedynczym odstępem, opisujące kolejnych Bajtołazów: - czas potrzebny na pokonanie mostu przez Bajtołaza () oraz - waga Bajtołaza ().

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę naturalną oznaczającą minimalny czas przeprawy wszystkich Bajtołazów przez most.

Przykład

Dla danych wejściowych:

100 3
24 60
10 40
18 50

poprawną odpowiedzią jest:

42

Autor zadania: Piotr Stańczyk.