K. Сколько весов достижимо

Как классная задача K, но вопрос другой: сколько различных суммарных весов от $1$ до $W$ можно набрать?

Битсет считает это тем же способом: после всех сдвигов достаточно посчитать единичные биты в первых $W + 1$ позициях, не считая нулевую.

У std::bitset для этого есть готовый метод count(). Если считать вручную, пригодится __builtin_popcountll по словам — но не забудьте обнулить биты за границей $W$, иначе они попадут в ответ.

Первая строка содержит числа $N$ ($1 \le N \le 2000$) и $W$ ($1 \le W \le 2 \cdot 10^6$).

Вторая строка — $N$ чисел $w_i$ ($1 \le w_i \le 2000$).

Одно число — количество достижимых весов от 1 до $W$.