304004 - 取款机

银行计划安装一台取款机,这台机器使用了N种不同面值的钞票,比如N=3,n_1=10,D_1=100,n_2=4,D_2=50,n_3=5,D_3=10表示机器有3种钞票,即10张100元的钞票,4张50元的钞票,5张10元的钞票。

现给定一个数字金额,试找出能够用这些钞票拼凑成的最接近且小于该数字金额的值。

输入

输入有多组数据,每组数据的格式为:cash N n_1 D_1 n_2 D_2…n_N D_N。其中cash(0\le cash\le100000)是给定的数字金额,N(0\le N\le10)表示钞票有多少种,n_k(0\le n_k\le1000,k=1~N)表示面值为D_k(1\le D_k\le1000)的钞票的张数。

输出

每组数据一行答案。

样例

输入

735 3 4 125  6 5  3 350
633 4  500 30  6 100  1 5  0 1
735 0
0 310 100  10 50  10 10

输出

735
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题