状压DP，思路：枚举合法状态，在每次更新Fi时，判断当前子集是否是i的合法子集，v记录最大时间，k表示是从哪里转移过来的 转移式Fi = min Fk + vj; code:

#include<cstdio>
#include<iostream>
using namespace std;

const int MAXN = 1e7 + 17;
const int INF = 1e9 + 1;

int F[MAXN],t[MAXN],w[MAXN],s[MAXN],v[MAXN],s0,n,W;

void gets()
{
	int cost,time;
	for(int i = 1;i < (1 << n);i += 1)
	{
		cost = 0;
		time = 0;
		for(int j = 1;j <= n;j += 1)
		{
			if((i & (1 << (j - 1))) == 0)continue;
			cost += w[j];
			time = max(time,t[j]);
			if(cost > W)break;
		}
		if(cost <= W){
			s[++s0] = i;
			v[s0] = time;
		}
	}
}

bool check(int u,int v)
{
	for(int i = 1;i <= n;i += 1)
		if((u >> (i - 1)) && !(v >> (i - 1)))return 0;
	return 1;
}

int main()
{
	cin >> W >> n;
	for(int i = 1;i <= n;i += 1)
		cin >> t[i] >> w[i];
	gets();
	F[0] = 0;
	for(int i = 1;i < (1 << n);i += 1)
	{
		F[i] = INF;
		for(int j = 1;j <= s0;j += 1)
		{
			if(s[j] > i)break;
			if(!check(s[j],i))continue;
			int k = i - s[j];
			F[i] = min(F[i],F[k] + v[j]);
		}
	}
	cout << F[(1 << n) - 1] << endl;;
	return 0;
}