4050 - 基础算法-贪心算法:西红柿首富的烦恼升级版
Time Limit : 1 秒
Memory Limit : 128 MB
王多鱼获得了一笔的奖金X,要求购买最少的商品把钱花光,即没有零钱剩下,否则奖金会被没收。
Input
输入:
第一行:一个整数k:商品的种类(每个种类商品个数有限,不超过100件);
第二行:第i类商品的价值a[i];
第三行:第i类商品的数量b[i];
第四行:一个整数m:奖金总额
Output
输出:
最少商品数量
Examples
Input
7 1 2 5 10 20 50 100 5 5 5 5 5 5 1 288
Output
9