Találtunk egy kincsesbarlangot, melyben $n$ darab ‐ különböző értékű és tömegű ‐ kincs van. Ezekből szeretnénk néhányat $w$ kilogramm teherbírású hátizsákunkba rakni úgy, hogy a bepakolt kincsek értékének összege a lehető legnagyobb legyen.
Írjunk programot, amely kiszámítja a legnagyobb bepakolható értéket. A program bemenetének első sorában $n$, második sorában $w$ áll. Ezután $n$ további sor következik, mindegyik egy kincs tömegét és értékét tartalmazza. (Az adatok ezúttal is helyesek lesznek, az ellenőrzéstől eltekinthetünk.) A program kimenete egyetlen szám, a legnagyobb bepakolható érték.
Példa: ${\displaystyle \begin{array}{cc}{\displaystyle \text{ Input }}\hfill & {\displaystyle \text{ Output}}\hfill \\ {\displaystyle \text{6 }}\hfill & {\displaystyle \text{ 1030}}\hfill \\ {\displaystyle \text{10 }}\hfill & {\displaystyle }\hfill \\ {\displaystyle \text{3 300 }}\hfill & {\displaystyle }\hfill \\ {\displaystyle \text{2 175 }}\hfill & {\displaystyle }\hfill \\ {\displaystyle \text{5 540 }}\hfill & {\displaystyle }\hfill \\ {\displaystyle \text{3 310 }}\hfill & {\displaystyle }\hfill \\ {\displaystyle \text{11 15000 }}\hfill & {\displaystyle }\hfill \\ {\displaystyle \text{4 420 }}\hfill & {\displaystyle }\hfill \end{array}}$

További teszt-adatok és részletes beküldési útmutató a KöMaL honlapján, a http://www.komal.hu/verseny/2004-10/inf.h.shtml címen található.