Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int g,n;

#define MAXN 17

int t[MAXN],w[MAXN];

int f[1 << MAXN],T[1 << MAXN],W[1 << MAXN];

int main()

{

	scanf("%d%d",&g,&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&t[i],&w[i]);

	}

	int tot = (1 << n) - 1;

	for(int b = 1;b <= tot;++b)

	{

		for(int i = 1;i <= n;++i)

		{

			if(b & (1 << (i - 1)))

			{

				T[b] = max(T[b],t[i]);

				W[b] += w[i];

			}

		}

	}

	memset(f,0x3f,sizeof(f));

	f[0] = 0;

	for(int b = 0;b <= tot;++b)

	{

		for(int s = tot ^ b;s != 0;s = (s - 1) & (tot ^ b))

		{

			if(W[s] <= g)f[b | s] = min(f[b | s],f[b] + T[s]);

		}

	}

	cout << f[tot] << endl;

	return 0;

}