Рюкзак с ценностями

У каждого из $n$ предметов есть вес и ценность. Выберите набор суммарного веса не больше $W$ с наибольшей суммарной ценностью; каждый предмет доступен в одном экземпляре.

В первой строке $n$ и $W$ ($1 \le n \le 1000$, $1 \le W \le 10^5$). В каждой из следующих $n$ строк — вес $w_i$ и ценность $v_i$ ($1 \le w_i \le 10^5$, $1 \le v_i \le 10^9$).

Выведите наибольшую суммарную ценность.