|
|
VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004 |
Zadanie F - Pakowanie plecaka |
Mały Jacuś jedzie wkrótce na obóz harcerski. Jak zawsze zastanawia się co zapakować do plecaka, który przecież ma ograniczony udźwig, tak aby spakowane przedmioty były jak najbardziej użyteczne. Chłopiec jest w posiadaniu pewnej liczby przedmiotów, z których każdy jest opisany dwiema liczbami: wartość (odzwierciedlająca użyteczność przedmiotu) oraz ciężar. Niektóre przedmioty są Jacusiowi niepotrzebne, a wręcz mogą przeszkadzać, stąd wartości przedmiotów mogą być mniejsze lub równe 0. Przy pakowaniu chłopcu zależy przede wszystkim na tym, żeby uzyskać upakowanie maksymalne, w sensie możliwości dołożenia czegoś więcej. Tj. chce tak załadować plecak (choćby nawet zbędnymi rzeczami), by nie móc dołożyć, żadnego innego przedmiotu, będącego w jego posiadaniu, bez wyjmowania przedmiotów już włożonych (cóż... harcerzem to on jest może początkującym, ale za to jest zafascynowany popisami strongmanów). Dopiero spośród wszystkich upakowań maksymalnych chce wybrać upakowanie o możliwie największej sumie wartości przedmiotów.
Mając daną liczbę przedmiotów posiadanych przez Jacusia oraz ich wartości i ciężary, należy podać jaką łącznie największą wartość można uzyskać, przy założeniu maksymalnego upakowania.
W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu zestawu znajdują się dwie liczby całkowite N i M (1 ≤ N ≤ 1.000, 1 ≤ M ≤ 8.000), oznaczające odpowiednio liczbę przedmiotów Jacusia oraz maksymalny udźwig plecaka. Kolejne N wierszy zestawu to opisy przedmiotów. Każdy nich składa się z dwóch liczb całkowitych W i V (1 ≤ W ≤ M, –1.000.000 ≤ V ≤ 1.000.000), oznaczających ciężar oraz wartość przedmiotu.
Dla każdego zestawu danych należy zapisać, w osobnym wierszu, jedną liczbę całkowitą - największą sumaryczną wartość przedmiotów jaką da się zapakować zgodnie z preferencjami Jacusia.
3 2 2 2 3 1 4 3 8 3 3 4 4 6 6 3 10 1 4 1 -3 1 2
4 7 3