思路

完全背包模版题。 我们设 $dp_i$ 表示前 $i$ 分钟可以采取的最大值，不难推出方程为

$$dp_i=\max(dp_i,dp_{i-v}+w)$$

前者表示不选，后者表示选。

code

#include<bits/stdc++.h>
using namespace std;
const int N =1e7+5;
long long f[N];
int v[N],w[N];
int main(){
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
         for(int j=v[i];j<=m;j++)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
}