记忆化求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30005;
int n,m;
int v[N],p[N];
int f[30][N];
int in(){
	int x,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	for(x=0;c>='0'&&c<='9';c=getchar()){
		x=x*10+(c-'0');
	}
	return x*f; 
}
int dfs(int to,int lc){//to:当前物品 lc:剩余费用 
	if(f[to][lc]!=-1){
		return f[to][lc];
	}
	if(to>m){
		f[to][lc]=0;
	}
	int a1;
	int a2;
	a1=dfs(to+1,lc);
	if(lc>=v[to]){
		a2=dfs(to+1,lc-v[to])+v[to]*p[to];
	}
	return f[to][lc]=max(a1,a2);
}
int main(){
	memset(f,-1,sizeof(f));
	n=in();
	m=in();
	for(int i=1;i<=m;i++){
		v[i]=in();
		p[i]=in();
	}
	printf("%d\n",dfs(1,n));
	return 0;
}