问题 6042 --让人头疼的“双十一”

6042: 让人头疼的“双十一”

时间限制: 1 Sec  内存限制: 32 MB
提交: 396  解决: 117
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][40kb]

题目描述

双十一就这样轰轰烈烈的来了,对于一个买东西只靠网购的资深宅男小灰灰来说,这的确是个令人兴奋的事情。
而现在的小灰灰却是痛并快乐着,因为本就干瘪的钱包实在挤不出多少money用来购物了,谁叫他把钱都用来买纸了呢....话说钱到用时方恨少,小灰灰处在深深的忧虑中,不知道怎样才能用剩下的钱买到最有价值的东西,各位小伙伴你们能把他搞定这件事吗

输入

第一行一个整数T表示有T组测试数据(T<=50)。
接下来的T组测试数据:
第一行包含两个整数N和M,N表示小灰灰有多少钱,M表示有多少件物品(1<=M<=100)。
再二行包含M个整数,表示对应每个物品的价格。
第三行包含M个整数,表示对应每个物品的价值。
0<N,A,B<3000

输出

请帮助小灰灰使用仅有的钱购买物品,并使物品的总价值最大。输出最大值。

样例输入

4
10 5
2 3 7 7 3
4 3 5 6 4
10 8
5 6 4 2 3 7 1 8
5 3 5 3 5 7 5 7
20 7
10 15 4 5 6 8 5
15 14 9 2 2 6 7
10 3
7 4 5
16 7 10

样例输出

Case #1: 11
Case #2: 18
Case #3: 31
Case #4: 17

提示

来源

[提交][状态]