Рюкзак перебором

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

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

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

Одно число.

Отсечение простое: если предмет не влезает, ветку «взять» можно не рассматривать вовсе.