Description
一家银行计划安装一台取款机，这台机器能够按要求的现金金额输出适当的钞票。
这台机器使用了N种不同面值的钞票：Dk，k=1...n，而且对于每种面值的钞票Dk，机器里面都有Nk张。
例如：n=3，n1=10，d1=100，n2=4，d2=50，n3=5，d3=10
意思是机器有3种不同面值的钞票，10张100美元的、4张50美元的、5张10美元的钞票。
编写一个程序，要求在输入取款金额时，根据机器的可用钞票供应量计算出可以有效交付的最大现金量。（最大现金量必须不超过输入金额）
Input
输入中的每个数据集代表一个特定的取款事务，其格式为：
取款金额 n N1 D1 N2 D2 ...... Nn Dn
其中:
0 <= 取款金额 <= 100000, 表示是请求的取款金额
0 <= n <= 10，表示钞票面值种类数;
0 <= Nk <= 1000是Dk面额的可用票据数量，1 <= Dk <= 1000，k=1...n。
输入的数字之间可以自由出现空格。
Output
对于每一组数据，程序将结果打印到单独一行的标准输出，如下例所示。
735 3 4 125 6 5 3 350
633 4 500 30 6 100 1 5 0 1
735 0
0 3 10 100 10 50 10 10