rt，代码如下

#include<iostream>
#include<queue>
#include<algorithm>
#include<stack>
#include<cmath>
#include<cstring>
#include<vector>
#include<bitset>
#include<map>
#include<cstdio>
#include<stdlib.h>
#include<string>
#pragma warning(disable : 4996)
#define ll long long
#define ret return
#define ms3f(a) memset(a,0x3f,sizeof(a));
#define ms0(a) memset(a,0,sizeof(a));
#define NO cout<<"NO"
#define YES cout<<"YES"
using namespace std;
int w[10005], val[10005];
int dp[1000005];
int main()
{
    int t, m, res = -1;
    cin >> t >> m;
    for (int i = 1; i <= m; i++) {
        cin >> w[i] >> val[i];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = t; j >= 0; j--) {
            for (int k = 0; t >= k * w[i]; k++) {
                if (j >= k * w[i]) {
                    dp[j] = max(dp[j - k * w[i]] + k * val[i], dp[j]);
                }
            }
        }
    }
    cout << dp[t] << endl;;
    return 0;
}