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

错的样例是： in: 12000 18

2758 5

3500 3

1200 2

430 4

530 3

239 3

2630 4

500 2

1120 3

1430 3

1420 5

400 1

1500 3

666 3

521 4

2430 3

1400 2

3410 4

我的cout: 48854 out:51161