90分求调

#include <bits/stdc++.h> 
using namespace std;
int mp[101][1001];
int a[1000000], b[10000000];
int main(){
	int i, j, n, m;
	cin >> m >> n;
	for(i = 1; i <= n; ++i){
		cin >> a[i] >> b[i];
		b[i] *= a[i]; 
	}
	for(i = 1; i <= n; ++i){
		for(j = m; j >=1 ; --j){
			if(a[i] > j) mp[i][j] = mp[i - 1][j];
			else mp[i][j] = max(mp[i - 1][j], mp[i - 1][j - a[i]] + b[i]);
		}
	}
    cout << mp[n][m];
return 0;
}