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.
Jaś i Małgosia wyjeżdżają na wycieczkę. Chłopiec, chcąc zaimponować koleżance, postanowił spakować ich rzeczy do jednego plecaka. Co więcej, im cięższy ten plecak będzie, tym lepsze zrobi wrażenie. Oczywiście Jaś nie może bez zastanowienia zapakować wszystkich rzeczy, które znajdzie w domu - przecież plecak mógłby się wtedy porwać (cóż to byłby za wstyd!).
Ponadto Jaś nie może dopuścić do sytuacji, w której np. zabrałby radio, ale zostawił baterie, albo wziął statyw, ale zapomniał aparatu. Dla każdego przedmiotu Jaś albo określił inny przedmiot , bez którego przedmiot byłby bezużyteczny, albo po prostu zaznaczył, że jest przedmiotem, który sam w sobie jest przydatny.
Pomóż naszemu bohaterowi i oblicz, jak ciężką zawartość plecaka może uzyskać, nie przekraczając jego maksymalnego udźwigu i nie zabierając żadnego bezużytecznego przedmiotu.
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite i (, ), oznaczające liczbę przedmiotów, których zabranie rozważa Jaś, oraz udźwig plecaka w kilogramach - jeśli zapakujemy przedmioty o sumarycznej masie przekraczającej , plecak porwie się.
Zakładamy, że przedmioty są ponumerowane liczbami od 1 do . W kolejnych wierszach znajdują się opisy przedmiotów - opis przedmiotu o numerze składa się z dwóch liczb i (, ), oznaczających kolejno numer przedmiotu, który musi być w plecaku, aby można było zapakować tam przedmiot (jeśli , to przedmiot można zapakować bezwarunkowo), oraz masę przedmiotu w kilogramach.
Twój program powinien wypisać na wyjście jedną liczbę całkowitą: maksymalną masę zawartości plecaka (w kilogramach), jaką Jaś może uzyskać.
Dla danych wejściowych:
7 11 0 3 0 1 2 3 2 2 4 4 5 3 5 2
poprawną odpowiedzią jest:
10
Autor zadania: Piotr Sankowski.