W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
Napisz program, który:
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 ().
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.
Dla danych wejściowych:
100 3 24 60 10 40 18 50
poprawną odpowiedzią jest:
42
Autor zadania: Piotr Stańczyk.