#include<bits/stdc++.h>
using namespace std;
int n,t,maxx,a[105],b[105],c[105];

void dfs(int x,int s)
{
    if(x>t)return;
    for(int i=1;i<=n;i++)
    if(!c[i]&&t-x+1>a[i])
    {
        c[i]=1;
        if(x+a[i]<=t)maxx=max(maxx,s+b[i]);
        dfs(x+a[i],s+b[i]);
        c[i]=0;
    }
}

int main()
{
	cin>>t>>n;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	dfs(0,0);
	cout<<maxx;
    return 0;
}

1,2,3AC; 其余TLE。