#include<bits/stdc++.h>
using namespace std;
#define int long long
pair<int,int> findans(vector<pair<int,int>>& v,int i,int budget,int cost,vector<vector<pair<int,int>>>& dp,int value)
{
   
    //cout<<"for i = "<<i<<" and cost = "<<cost<<" and value = "<<value<<endl;
    if(i<0)
    {
        //cout<<"Returning"<<endl;
        return make_pair(value,cost);
    }
    if(dp[i][cost].first!=-1)
    {
        //cout<<"Value is present as - "<<dp[i][cost].first<<endl;
        return dp[i][cost];
    }
    if(cost+v[i].first<=budget)
    {
       
        pair<int,int> x=findans(v,i-1,budget,cost+v[i].first,dp,value+v[i].second);
        pair<int,int> y=findans(v,i-1,budget,cost,dp,value);
       
        if(x.first==y.first)
        {
            if(x.second<y.second)
            return dp[i][cost]=x;
            else
            return dp[i][cost]=y;
           
        }
        else
        if(x.first>y.first)
        return dp[i][cost]=x;
        else
        return dp[i][cost]=y;
    }
    else
    {
        return dp[i][cost]=findans(v,i-1,budget,cost,dp,value);
    }
   
}
 
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int budget,n;
    cin>>budget>>n;
    while(budget!=0 && n!=0){
    vector<pair<int,int>> v;
    for(int i=0;i<n;i++)
    {
        int cost;
        int enjoy;
        cin>>cost>>enjoy;
        v.push_back(make_pair(cost,enjoy));
    }
    //sort(v.begin(),v.end(),compare);
    int cost=0;
    int newcost=0;
    vector<vector<pair<int,int>>> dp(101,vector<pair<int,int>>(501));
    for(int i=0;i<=100;i++)
    {
        for(int j=0;j<=500;j++)
        {
            dp[i][j].first=-1;
        }
    }
    pair<int,int> ans=findans(v,n-1,budget,cost,dp,0);
    cout<<ans.second<<" "<<ans.first<<endl;
    //cout<<dp[9][0].first<<endl;
    cin>>budget>>n;
    }
}