阿巴阿巴

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