DP602 零钱凑额

难度梯度：T3-｜训练重点：完全背包最小值

题目描述

给定 N 种不同正整数面值，第 i 种硬币可以使用任意多枚。求恰好凑出金额 T 的最少硬币数；若无法凑出，输出 -1。

每种面值可使用任意多枚，允许不同面值相同。只计最少总枚数，不要求输出具体方案。

输入格式

第一行 N T；第二行 N 个正整数面值 v_i。

输出格式

输出最少枚数或 -1。

样例输入

3 11
1 5 7

样例输出

3

样例说明

可用 5+5+1。

数据范围

1≤N≤100；1≤T≤10^5；1≤v_i≤T。

子任务

30 分：T≤1000；30 分：所有 v_i 相同；40 分：无附加限制。