hzCPPOJ

零花钱2

时间限制:  0 s      内存限制:   128 MB
提交:18     正确:10     分值:99

题目描述

作为创造产奶纪录的回报,Farmer John决定开始在圣诞节给Bessie发一个额外的零花钱C (1 <= C <= 1000)

FJ有一些硬币,一共有N (1 <= N <= 20)种不同的面额,数量不限。请帮他计算他最少能用多少枚硬币凑出这个圣诞节的额外零花钱(不能多也不能少)?

输入

*  第一行:  两个由空格隔开的整数:  N  和  C

*  第2到第N+1行:  每一行有1个整数表示一个面额的硬币:硬币面额V  (1  < =  V  < =  1000)

输出

*  第一行:  一个单独的整数,表示Farmer  John最少能用多少枚硬币凑出这个圣诞节的额外零花钱,若凑不出来则输出-1

样例

样例输入:
3 6 10 1 5
样例输出:
2
样例输入:
3 11 1 2 5
样例输出:
3

提示

FJ想要给Bessie六美分额外零花钱。他有无限的1美分硬币,5美分硬币,和10美分硬币。 

FJ可以用最少2个硬币(·个5美分硬币和一个1美分硬币)来凑出这个零花钱。

来源/分类

DP