#include <stdio.h>
#define M 1001

int path[M][M];//标记物品选择情况
int cost[M],val[M];
int dp[M];//动态规划数组

int main()
{
    int m,n,i,j,k;
    while(scanf("%d %d",&m,&n)!=EOF){
        for(i=0;i<n;i++){
            scanf("%d %d",&cost[i],&val[i]);
        }
        for(j=0;j<=m;j++){
            dp[j]=0;
        }
        for(i=0;i<M;i++){
            for(j=0;j<M;j++){
                path[i][j]=0;
            }
        }

        for(i=0;i<n;i++){//开始动态规划
            for(j=m;j>=cost[i];j--){//逆序，可参考上一轮结果
                if(dp[j]<dp[j-cost[i]]+val[i]){
                    dp[j]=dp[j-cost[i]]+val[i];
                    for(k=0;k<M;k++){//将物品选择情况也克隆
                        path[j][k]=path[j-cost[i]][k];
                    }
                    path[j][i]=1;
                }
            }
        }

        if(dp[m]==0){
            printf("0\n");
            continue;
        }
        printf("%d\n",dp...