> #include<iostream>
> #include<cstdio>
> #include<cmath>
> #include<cstring>
> #include<string>
> using namespace std;
> int a[20],num[20];
> int dp[100005];
> int main()
> {
> 	int c,n,i,j,k;
> 	while(scanf("%d%d",&c,&n)==2)
>     {
>         memset(a,0,sizeof(a));
>         memset(num,0,sizeof(num));
>         memset(dp,0,sizeof(dp));
>         for(i=1;i<=n;i++) scanf("%d%d",&num[i],&a[i]);
>         for(i=1;i<=n;i++)
>             for(j=a[i];j<=c;j++)
>                 for(k=1;k<=num[i];k++)
>                 {
>                     if(j>=k*a[i])
>                     {
>                         dp[j]=max(dp[j],dp[j-k*a[i]]+k*a[i]);
>                     }
>                     else break;
>                 }
>         printf("%d\n",dp[c]);
>     }
>     return 0;
> }