U410504 【模板】完全背包(加强版)

题目描述

有 $n$ 种物品,每种物品都有无限多个并且有重量 $w_i$。 你有一个背包,背包有一个上限 $V$,你只能装入总重量不超过 $V$ 的物品。 问你最后能得到多少种不同质量。

输入格式

第一行,两个整数 $n$ 和 $V$。 第二行有 $n$ 个整数 $w_i$,表示每个物品的重量。

输出格式

一个整数,表示答案。

说明/提示

#### 样例解释 可以得到的质量有 $0$,$2$,$4$,$6$,$8$,$10$。 #### 数据范围 对于所有测试数据,$1\le n,w_i,V\le 4\times 10^5$。 对于 $20\%$ 的数据,$1\le n,V\le 1000$。