Polish version    English version  
 


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XI Olimpiada Informatyczna 2003/2004

Zadanie: prz

Przeprawa

Zawody II stopnia  
Plik źródłowy: prz.xxx (xxx=pas,c,cpp)
Limit pamięci: 32 MB

Alternatywne formaty: PostScript | PDF

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: w - określającą maksymalne dopuszczalne obciążenie mostu (100 <= w <= 400) oraz n - równą liczbie Bajtołazów (1 <= n <= 16). W kolejnych n wierszach znajdują się po dwie liczby całkowite oddzielone pojedynczym odstępem, opisujące kolejnych Bajtołazów: t - czas potrzebny na pokonanie mostu przez Bajtołaza (1 <= t <= 50) oraz w - waga Bajtołaza (10 <= w <= 100).

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

prawidłową odpowiedzią jest:

42



Wersja do druku