RT

dfs 乱搞过了。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int T,m,ans=0,zt,zv,cnt=0;
const int N=10000000;
struct grass
{
	int t;
	int v;
};
grass a[110];
bool cmp(grass x,grass y)
{
	return x.v*y.t>y.v*x.t;
}
void dfs(int id,int kt,int kv)
{
	if(cnt>=N) return;
	if(id>m)
	{
		if(kt>T)
			return;
		ans=max(ans,kv);
		return;
	}
	if(kt>T||a[id].v*(T-kt)/a[id].t+kv+bool(a[id].v*(T-kt)%a[id].t)<ans)
		return;
	cnt++;
	ans=max(ans,kv);
	if(cnt>=N)
		return;
	dfs(id+1,kt+a[id].t,kv+a[id].v);
	dfs(id+1,kt,kv);
	return;	
}
int main(){
	scanf("%d%d",&T,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&a[i].t,&a[i].v);
	sort(a+1,a+m+1,cmp);
	dfs(1,0,0);
	printf("%d",ans);
	return 0;
}