#include<cstdio>
#include<iostream>
using namespace std;
int price[102];
int fun[102];
int dp[502][102];
int keep[502][102];
int bud[502][102];
int main()
{
int parties,budget;
scanf("%d" "%d",&budget,&parties);
while(!(parties == 0 && budget == 0))
{
for(int i=1;i<=parties;i++)
{
scanf("%d" "%d",&price[i],&fun[i]);
}
for(int j =0;j<=budget;j++)
{
dp[0][j]=0;
bud[0][j]=0;
}
for(int i=0;i<=parties;i++)
{
dp[i][0]=0;
bud[i][0]=0;
}
for(int i =1;i<=parties;i++)
{
int x,y,m,n;
for(int j=1;j<=budget;j++)
{
if(price[i]<=j)
{
x = fun[i] + dp[i-1][j-price[i]];
m= price[i] + bud[i-1][j-price[i]];
n=bud[i-1][j];
y= dp[i-1][j];
if(x>y)
{
dp[i][j]=x;
keep[i][j]=1;
bud[i][j]=m;
}
else if(x==y)
{
dp[i][j]=x;
bud[i][j] = m<n?m:n;
if(m>n)
keep[i][j]=0;
else
keep[i][j]=1;
}
else
{
dp[i][j]=y;
keep[i][j]=0;
bud[i][j]=n;
}
}
else
{
y=dp[i-1][j];
n=bud[i-1][j];
dp[i][j]=y;
keep[i][j]=0;
[quote][quote][quote][/quote][/quote][/quote]bud[i][j]=n;
}
}
}
printf("%d %d\n",bud[parties][budget],dp[parties][budget]);
scanf("%d" "%d",&budget,&parties);
}
return 0;
}