Рюкзак таблицей

У туриста рюкзак на $w$ килограммов и $n$ предметов с известным весом и ценностью.

Наберите наибольшую суммарную ценность, не перегрузив рюкзак. Предметы неделимы, каждый берётся не больше одного раза.

В первой строке числа $n$ от $1$ до $100$ и $w$ от $0$ до $10^4$. В следующих $n$ строках по два числа: вес от $1$ до $10^4$ и ценность от $1$ до $10^9$.

Одно число.

Состояние — «наибольшая ценность, помещающаяся в рюкзак вместимости $t$, если рассмотрены первые $i$ предметов». Хранить всю таблицу не нужно, хватает одной строки — но тогда веса надо перебирать от большего к меньшему, иначе один предмет попадёт в рюкзак несколько раз.