恰好装满的最少件数

难度：T2

【知识点：零一背包、状态初始化】

前置知识：数组、循环、二维状态到一维滚动。

题目描述

有 $n$ 件体积为 $w_i$ 的物品，每件至多选一次。求恰好装满容量 $W$ 所需的最少件数。无法恰好装满输出 -1。$W=0$ 时空选择合法，需要 $0$ 件。不同编号的物品即使属性相同，仍各有一件。

输入格式

第一行两个整数 $n,W$。第二行 $n$ 个整数 $w_1,\ldots,w_n$。

输出格式

一行一个整数，表示恰好装满的最少件数；无合法方案则输出 -1。

样例输入

3 6
6 3 3

样例输出

1

样例解释

选择体积为 $6$ 的一件即可，不必选择两件体积为 $3$ 的物品。

数据范围

$1\le n\le100$，$0\le W\le2000$，$1\le w_i\le2000$。