1321: 张孟思买玩具

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：16 Solved：4

Description

张孟思老师带着女儿去买玩具，张孟思老师不喜欢移动支付，喜欢硬币支付，但是她又不喜欢清点硬币，因此她讲究最少数量的硬币易手，也就是她用来支付的硬币的数量加上他收到的找零的硬币数量要最小化（即找回的和付出的硬币的总枚数最少）。请帮助他确定这个最小值是多少。

张孟思老师想给女儿买T（1≤T≤10000）元的玩具。货币体系有N(1≤N≤100）种不同的硬币，其面值为V1、V2、…、VN（1≤V≤120）。张孟思老师有面值为V1的硬币C1枚，面值为V2的硬币C2枚……面值为VN的硬币CN枚（0≤C≤10000）。玩具店的老板则拥有所有的硬币无限枚，并且总是以最有效的方式进行找零。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

本题包含多组测试用例。每组测试用例的第一行是两个用空格分隔的整数N和T，第二行给出N个用空格分隔的整数，分别表示V1、V2、…、VN，第三行给出给出N个用空格分隔的整数，分别表示C1、C2、…、CN。

Output

对每组测试数据，输出一行，为一个整数，表示在支付和找零中使用硬币的最少数量。

Sample Input Copy 

3 70
5 25 50
5 2 1
10 3949
37 40 42 44 51 59 68 72 90 92
862 552 858 751 109 291 111 87 394 369

Sample Output Copy 

3
44

Source/Category