3.金币获取
题目描述
XZH 有一种研究,那就是机器。
他研究并发明了 n 台机器,用 1∼n 标号。每台机器有两个属性。对于第 i 台机器,
有 ai ,bi 两个属性,解释见下文。
现在,XZH 要把自己的银币换成金币,他的做法是将这些银币依次使用这 n 台机器。如果
他要使 x 枚银币通过第 i 台机器,那么会发生下面的事情。
如果 x≤ai ,则银币数清空,不会获得新的金币。
如果 x>ai ,则银币数会减少 ai ,当银币数 x=x−ai 之后,XZH 会获得 x×bi 枚
金币。
举个例子。
XZH 有 9 枚银币,他要通过 (a1 ,b1 )=(5,3),(a2 ,b2 )=(10,10) 的两台机器
对于第一台机器,由于 9>5,所以这些银币可以通过这一台机器,并且剩下 4 枚银币。所
以他获得了 4×3=12 枚金币。
对于第二台机器,由于他只有 4 枚银币,4≤10,所以他的所有银币会被第二台机器消耗掉,
不会获得金币。
综上所述,他会获得 12 枚金币。
现在,他想知道,如果他想用这 n 台机器获得至少 k 枚金币,他至少需要多少枚银币?
本题采用多组数据。
输入格式
第一行,输入一个整数 T,下面有 T 组数据。
对于每一组数据:
第一行一个整数 n,k。
第二行,n 个整数,第 i 个表示 ai 。
第三行,n 个整数,第 i 个表示 bi 。
输出格式
对于每一组数据,输出一个 ans,用换行隔开,代表 XZH 获得至少 k 枚金币需要银币数量
的最小值。
样例
样例输入 1 样例输出 1
2 9 7
2 12
5 10
3 10
2 12
4 2
3 4
样例说明
样例 1 解释:XZH 开始有 9 枚银币。
通过第一个机器 (5,3),他剩余 4 枚银币,获得 4×3=12 枚金币。
由于 4≤10,所以通过第二台机器的时候不会产生收益。
所以,他有 9 枚金币。
提示
对于 50% 的数据 1≤n≤1000,1≤k≤1000
对于 100% 的数据 1≤T≤10,1≤n≤104,1≤k≤109,0≤ai ≤109,0≤bi ≤10,bi >0。
c++求解