var

s:array[0..30001]of integer；

i,a,b,n,m,j:longint；

begin

readln(n,m)；

for i:=1 to m do

begin

readln(a,b)；

b:=a*b；

for j:=n downto a do

if s[j-a]+b>s[j] then s[j]:=s[j-a]+b；

end；

writeln(s[n])；

end.

#include<iostream>

#define MAXN 30000

#define MAXM 25

using namespace std；

#define fin cin

#define fout cout

//ifstream fin ("happy.in")；

//ofstream fout ("happy.out")；

int main (void)

{

int dp[MAXN],v[MAXM],w[MAXM]；

int n,m；

fin>>n>>m；

for (int i=1；i<=m；i++)

fin>>v[i]>>w[i]；

memset(dp,0,sizeof(dp))；

for (int j=1；j<=m；j++)

for (int i=n；i>=v[j]；i--)

if (dp[i-v[j]]+v[j]*w[j]>dp[i])

dp[i]=dp[i-v[j]]+v[j]*w[j]；

fout<<dp[n]<<endl；

return 0；

}