|
||||||||||||||||||||||||||||||||||||||||
|
Zadanie: prz Przeprawa
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. ZadanieNapisz program, który:
WejściePierwsza 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ścieW 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ładDla danych wejściowych: 100 3 24 60 10 40 18 50 prawidłową odpowiedzią jest: 42 Wersja do druku |