#include<bits/stdc++.h>
using namespace std;

int main()
{
    int s,n;
    while(cin>>s>>n)
    {
    int a[1001][101]={0};
    int w[1001]={0},v[1001]={0};
    int c[101]={0}; 
    int k=1;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=s;j++)
        {
            //a[i-1][j-w[i]]+v[i]是将i物品装入背包
            //a[i-1][j]是不装 
            if((j-w[i])>=0)
            {
                    if(a[i-1][j]>=(a[i-1][j-w[i]]+v[i]))
                    {
                        a[i][j]=a[i-1][j];
                    }
                    else
                    {
                        a[i][j]=a[i-1][j-w[i]]+v[i];
                    }
            }
            else
            {
                a[i][j]=a[i-1][j];
            }
        
            
        }
    }
    if(a[n][s]!=0)
    {
            printf("%d\n",a[n][s]);
       ...