#2587. 找零钱

找零钱

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

农夫John\red{John}想到镇上买些补给。为了高效地完成任务,他想使硬币的转手次数最少.即使他交付的硬币数与找零得到的的硬币数最少。

John\red{John}想要买价格为T(1<=T<=10000)\red{T(1<=T<=10000)}的东西。有N(1<=n<=100)\red{N(1<=n<=100)}种货币参与流通,面值分别为V1,V2..Vn(1<=Vi<=120)\red{V1,V2..Vn (1<=Vi<=120)}John\red{John}Ci\red{Ci}个面 值为Vi\red{Vi}的硬币(0<=Ci<=10000)\red{(0<=Ci<=10000)}

我们假设店主有无限多的硬币,并总按最优方案找零。

输入格式

第一行: 两个整数 N\red{N }T\red{T }

第二行: N\red{N }个数,表示 V1,V2,..Vn\red{V1, V2, ..Vn}

第三行: N\red{N }个数,表示 C1,C2,..Cn\red{C1, C2, ..Cn}

输出格式

第一行: 一个整数,表示最优方案的转手次数,如无解输出1\red{-1}

样例

输入样例

3 70
5 25 50
5 2 1

输出样例

3

C++高级B1班03-背包DP

未参加
状态
已结束
规则
IOI
题目
14
开始于
2024-11-17 15:45
结束于
2024-12-8 11:45
持续时间
500 小时
主持人
参赛人数
31