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）的钞票的张数。

每组数据一行答案。