Problem Description

A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a requested cash amount. The machine uses exactly N distinct bill denominations, say Dk, k=1,N, and for each denomination Dk the machine has a supply of nk bills. For example,

 

N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10

 

means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each.

 

Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.

 

Notes:

  @ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc.

 

 

Input

The program input is from standard input. Each data set in the input stands for a particular transaction and has the format:

 

cash N n1 D1 n2 D2 ... nN DN

 

where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers in the input. The input data are correct.

 

 

Output

For each set of data the program prints the result to the standard output on a separate line as shown in the examples below.

 

 

Sample Input

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

 

Sample Output

735

630

0

0

 

Source

PKU

 

题意：在存款机里有几种不同面值的货币，各有自己的数量。给定一个取款值。

　　　求出小等于这个值的能取到的最大的数

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                
                 12 13 using namespace std;14 15 16 17 int n;18 int cash;19 struct my//建立结构体，存储每种货币的面值和张数；20 {21 int num;22 int money;23 24 } go[11];25 bool dp[111111];//建立辅助数组；26 27 bool cmp(my a,my b)28 {29 return a.money
                 
                  >cash)//录入最大的金额；37 {38 cin>>n;//录入钱币的种数；39 for (i=0; i
                  
                   >go[i].num>>go[i].money;41 sort(go,go+n,cmp);//进行排序42 for (i=1; i<=cash; i++)43 dp[i]=false;44 dp[0]=true;45 int big=0;//存储最大能取到的金额；46 for (k=0;k
                   
                    =0;j--)49 if (dp[j])//如果j金额可以取到50 {51 for (i=1; i<=go[k].num; i++)52 {53 int cur=j+i*go[k].money;54 if (cur>cash||dp[cur])//大于cash的数据不需要；扫过的金额不在进行操作；55 break;56 dp[cur]=true;57 big=max(big,cur);//跟新big；58 }59 }60 }61 for (i=cash; i>=0; i--) if (dp[i])62 {63 cout<
                    <