#include <bits/stdc++.h>
#define int long long
using namespace std;

int w,n,now,maxv,ans=0;

struct node
{
	int tim;
	int wei;
}a[20];

bool cmp(node x,node y)
{
	return x.tim>y.tim;
}

signed main()
{
	cin>>w>>n;
	for (int i=1;i<=n;i++)  cin>>a[i].tim>>a[i].wei;
	
	sort(a+1,a+n+1,cmp);
	maxv=a[1].tim;
	for (int i=1;i<=n;i++)
	{
		if (now+a[i].wei>w&&i!=n)
		{
			ans+=maxv;
			now=a[i].wei;
			maxv=a[i].tim;
		}
		else if (now+a[i].wei>w&&i==n)  ans+=maxv+a[i].tim;
		else if (i==n)  ans+=maxv;
		else now+=a[i].wei;
	}
	cout<<ans<<endl;
	
	return 0;
}

80分……第一个点WA了……

本蒟蒻觉得贪心可以用啊……