#include<bits/stdc++.h>
using namespace std;
const int N=30;
int v[N],w[N];
int main()
{
	int V,n;
	cin>>V>>n;
	for(int i=0;i<n;i++) //获取价格和重要度 
	{
		cin>>v[i]>>w[i];	
	} 
	int ans=0;
	for(int i=0;i<1<<n;i++) //枚举每种选择 
	{
		int sw=0,sv=0;
		for(int j=0;j<n;j++) //枚举当前选择的第j个物品 
		{
			if(i>>j&1)
			{
				sw+=w[j]*v[j];
				sv+=v[j];
			}
		}
		if(sv<=V) //可以更新答案 
		{
			ans=max(ans,sw);
		}
	}
	cout<<ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int M=30010;
int f[M];
int main()
{
    int V,n;
    cin>>V>>n;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=V;j>=v;j--)
        {
            f[j]=max(f[j],f[j-v]+v*w);
        }
    }
    cout<<f[V];
    return 0;
}