前面的大佬有很多状压了，由于n比较小，我想到了搜索，让蒟蒻提供一个搜索的代码吧，时间还是很理想的,时间最长的数据6ms过的；

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef pair<int, int> PII;
typedef long long LL;
const int N = 110, M = 5002;
int n, m,ans=1e9;
int  a[N], b[N],cnt[N],ma[N],len;
vector<int> g[N];
struct node
{
	int a, b;
}f[N];
bool st[N];

bool cmp(node x, node y)
{
	return x.b > y.b;
}
//cnt是每个组当前的重量，ma是每个组的最大时间，sum是当前每个组的最大时间的和，u是枚举到了第几个点；
void dfs(int u,int sum)
{
	if (sum >= ans) return;//剪枝优化

	if (u == m + 1)
	{
		ans = sum;
		return;
	}

	for (int i = 0; i <= len; i++)
	{
		if (cnt[i] + f[u].b <= n)
		{
			int t = sum;
			cnt[i] += f[u].b;
			int tt = ma[i];
			if (ma[i] < f[u].a) sum += (f[u].a - ma[i]);
			ma[i] = max(ma[i], f[u].a);
			dfs(u + 1, sum);//注意要恢复现场
			ma[i] = tt;
			cnt[i] -= f[u].b;
			sum = t;
		}
	}
	cnt[++len] = f[u].b;
	ma[len] = f[u].a;
	dfs(u + 1, sum+ma[len]);//新开一个组
	cnt[len] = 0;
	ma[len--] = 0;
}

int main()
{
	IOS;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> f[i].a >> f[i].b;
	sort(f + 1, f + m +1, cmp);
	//优化搜索顺序
	dfs(1,0);
	cout << ans << endl;
	return 0;
}