Wprowadzenie do zachłanności i dynamiki

18.10.2010 - Łukasz Zatorski
Trudność

Królewskie łupy


Nareszcie! Słynnemu Bajtockiemu złodziejowi - A. Bajtenowi udało się dostać do królewskich komnat. Droga do pałacu nie była łatwa - wymagała niezwykłej zręczności w trakcie wspinania się po dachu i akrobacji, których pozazdrosciłby mu nie jeden cyrkowiec. Bajten ma teraz dużo czasu na przejrzenie wszystkich kosztowności - król składa właśnie dyplomatyczną wizytę w sąsiednim państwie (razem ze swoją stutysięczną armią). Niestety A. Bajten może zapakować ograniczoną masę przedmiotów do swojej złodziejskiej torby - jeśli będzie ona za ciężka, nie będzie potrafił jej udźwignąć i po cichu wymknąć się z pałacu.

Nie zastanawiał się długo - szukał najdroższego przedmiotu (jeśli były dwa o tej samej wartości, wybierał lżejszy) i próbował go włożyć do swojej torby . Jeśli się mieścił – pakował, jeśli nie - odkładał go na bok i szukał kolejnego. I tak do czasu aż torba była pełna lub przejrzał wszystkie potencjalne łupy.

Po powrocie Bajten zaczął mieć wątpliwości co do swojej metody i poprosił Ciebie o obliczenie, o ile gorsza jest jego strategia od najlepszego możliwego wyniku. W tym celu wręczył Ci przykładowe listy przedmiotów wraz z ich wagami i wartościami.


Wejście

W pierwszej linii wejścia znajdują się dwie liczby naturalne $ n $ oraz $ p $ $ (0<n<1000, 0<p<10000) $ kolejno liczba przedmiotów w królewskich komnatach oraz pojemność złodziejskiej torby. W następnych n liniach znajdują się pary liczb całkowitych $ c_i $, $ w_i $ $ (0<c_i<1000, 0<w_i<1000) $ odpowiadających wartości oraz wadze $ i $-tego przedmiotu.



Wyjście:

Jedna liczba naturalna - różnica między największą możliwa osiągalną wartością torby a tą zapakowaną przez złodzieja.


Przykład:

Dla danych wejściowych:

6 10
5 3
6 2
7 3
10 7
8 4
9 5

Poprawnym wynikiem jest:

5

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.846155
Twoja ocena: Brak Ocena: 4.8 (13 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com