Набрать не больше предела

Даны веса $n$ предметов и предел $S$. Выберите подмножество с наибольшим суммарным весом, не превышающим $S$.

Веса до $10^{12}$ — рюкзак по суммам невозможен. $n \le 36$ — встреча посередине.

В первой строке $n$ и $S$ ($1 \le n \le 36$, $0 \le S \le 10^{15}$). Во второй — $n$ чисел $w_i$ ($1 \le w_i \le 10^{12}$).

Выведите наибольшую сумму, не превосходящую $S$.