| 问题描述 |
|---|
Alice拿纸币去商店买公仔，店员需要找m元零钱给Alice。已知可以用于找零的纸币共有a种不同的面额，分别是c1、c2、...、ca元，并且店里用于找零的每种面额的纸币数量是有限的，分别是d1、d2、...、da张。店员希望用尽可能少的纸币完成找零。问店员给Alice找零的纸币共有多少张？ |
| 输入描述 |
这是一道多组案例的题目。一个正整数n，表示案例的数量。（n<=100） 每组案例先是两个正整数m和a，表示需要找零m元钱，纸币有a种不同的面额；（m<=1000，a<=10） 然后是a个正整数c1、c2、...、ca，表示每种纸币代表的金额；（均不大于100） 然后是a个正整数d1、d2、...、da，表示每种纸币的最大数量。（均不大于100）
|
| 输出描述 |
针对每组案例，输出一个整数，表示找零需要的最少纸币张数。如果无解，输出-1。 每组案例输出完都要换行。 |
| 样例输入复制样例 |
4 7 3 1 2 5 3 3 3 10 3 1 2 5 3 3 3 10 3 5 2 1 1 3 3 11 3 2 3 5 2 1 1
|
| 样例输出 |
2 2 4 -1 |
| 相关 |