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

int dp[1005][105];
int mselect[1005][105];
int val[1005];
int money[1005];
int main() {
    int m,n;
    while (cin>>m>>n) {
        for (int i=1;i<=n;i++) {
            cin>>money[i];
            cin>>val[i];
        }
        memset(mselect,0,sizeof(mselect));
        memset(mselect,0,sizeof(dp));
        for (int i=1;i<=n;i++) {
            for (int j=0;j<=m;j++) {
                if (j>=money[i]) {
                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-money[i]]+val[i]);
                    if (dp[i-1][j]<dp[i-1][j-money[i]]+val[i]) {
                        mselect[i][j]=1;
                    }
                }
                else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        if (dp[n][m]==0) {
            cout<<"0"<<endl;
            continue;
        }
        vector<int> ans;
   ...