0
2424 最少的钱币
经验值:2000
时间限制:2000毫秒
内存限制:64MB
题目描述 Deion
农夫约翰要去商店买农场的补给。作为一个非常看重效率的人,他总是希望在买东西的过程中每次进出手的钱都尽量少,也就是说,农夫花的钱币数量和店员找的钱币数量的和尽可能小。请你帮助他计算这个和最小是多少。
农夫要去商店买T元的东西(1 ≤ T ≤ 10,000),所带钱币价值之和不超过15000,货币系统里有N种不同的钱币(1 ≤ N ≤ 100),每种钱币的价值分别为V1, V2, …, Vn(1 ≤ Vi ≤ 120)。农夫价值为Vi 的钱币分别带了Ci (0 ≤ Ci ≤ 10,000)个。店员每种价值的钱币都有无限个。店员也会以最有效率的方式找零。
输入描述 Input Deion
第一行:两个被空格分隔的整数:N和T
第二行:N个由空格分隔的整数:分别表示面额为 V1 V2 … Vn 的钱币
第三行:N个由空格分隔的整数:表示各种面额的钱币农夫分别有C1 C2 … Cn个
输出描述 Output Deion
一行:只有一个整数,表示农夫付钱用的钱币数量和找零得到的钱币数量的和的最小值,如果农夫的钱不足以付款和找出一定数量的零钱,则输出 -1
样例输入 Sample Input
3 70 5 25 50 5 2 1
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
Time Limit: 2000ms
Memory Limit: 64Mb
我还以为64KB
结果一看这么大