唉，一看就是一颗典型的01背包模板……

#include <bits/stdc++.h>
using namespace std;
int n, m;
int v, w;
int dp[1010];
int main(){
    cin >> m >> n;
    for(int i=1;i<=n;++i){
        cin >> v >> w;
        for(int j=m;j>=v;--j)
            dp[j]=max(dp[j],dp[j-v]+w);
    }
    cout << dp[m];
    return 0;
}