#define X 25

int c[X]={0};

void pro1 (int b);

void pro2 (int b,int d);

int chec (int b,int d);

void update (int a);

int sum1(int a[],int b[][2],int d);

int sum2(int a[],int b[][2],int d);

int main ()

{

int i,j,n,m;

int k=0;

int temp;

int check;

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

int data[n][2];

for (i=0;i<n;i++)

scanf("%d %d",&data[i][0],&data[i][1]);

int resu[2]={0};

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

{

update(i);

while (1)

{

temp=sum1(c,data,i);

if (temp<=m)

resu[1]=sum2(c,data,i);

if(resu[1]>resu[0])

resu[0]=resu[1];

check=chec(i,n);

if (check==1)

pro1(i);

else if (check==2)

pro2(i,n);

else if (check==3)

break;

}

}

printf("%d",resu[0]);

return 0;

}

int chec (int b,int d)

{

int i,p=0;

if (c[b-1]<d-1)

return 1;

else if (c[b-1]==d-1)

{

for (i=0;i<b;i++)

if (c[i]!=d-b+i)

p++;

if (p!=0)

return 2;

else

return 3;

}

}

void pro1 (int b)

{

c[b-1]++;

}

void pro2 (int b,int d)

{

int i,q;

for (i=0;i<b;i++)

if (c[b-1-i]!=d-1-i)

{

q=i+1;

break;

}

c[b-q]++;

for (i=b-q;i<b-1;i++)

c[i+1]=c[i]+1;

}

int sum1(int a[],int b[][2],int d)

{

int i;

int q=0;

for (i=0;i<d;i++)

q+=b[a[i]][0];

return q;

}

int sum2(int a[],int b[][2],int d)

{

int i;

int q=0;

for (i=0;i<d;i++)

q+=b[a[i]][0]*b[a[i]][1];

return q;

}

void update (int a)

{

int i;

for (i=0;i<X;i++)

c[i]=0;

for (i=0;i<a;i++)

c[i]=i;

}

#include <vector>

#include <algorithm>

typedef long long int lli;

using namespace std;

int * money;

int * value;

inline int max(int a, int b) {

if (a > b) return a;

else return b;

}

int maxValue(int endIndex, int maxMoney) {

if (endIndex == 1)

{

if (money[endIndex] <= maxMoney) return value[endIndex];

else return 0;

}

int result1 = maxValue(endIndex - 1, maxMoney);

int result2;

if(maxMoney - money[endIndex]>0)

result2=maxValue(endIndex - 1, maxMoney - money[endIndex]) + value[endIndex];

else result2 = 0;

return max(result1, result2);

}

int main() {

int maxMoney, itemCount;

cin >> maxMoney >> itemCount;

money = new int[itemCount + 1];

value = new int[itemCount + 1];

for (int i = 1; i <= itemCount; i++) {

cin >> money[i];

int weight;

cin >> weight;

value[i] = weight*money[i];

}

cout << maxValue(itemCount, maxMoney);

delete[] money;

delete[] value;

}