#include <iostream>
#include <string>
#include <fstream>
using namespace std;

ifstream fin("DATA3.txt");
ofstream fout("OUT3.txt");

int temp_rating;
int space,songs;   
int rating[100];
int size[100];    


void recurs(int currRate,int spaceFilled,int pos)
{     
     for (int fc = pos;fc < songs;fc++)
     {

         if ((spaceFilled + size[fc] <= space) && (currRate + rating[fc] > temp_rating))
         {
            temp_rating = currRate + rating[fc];                
         }
         

         recurs(currRate+rating[fc],spaceFilled+size[fc],fc+1);
     }
}

int main()
{
    string deleat;
    for (int tries = 1;tries <=5;tries++)
{
    fin >> space;
    fin >> songs;
    temp_rating = 0;
    
    for (int c = 0;c < songs;c++)

    {    
         fin >> deleat;
         fin >> rating[c];
         fin >> size[c];   
    }
    recurs(0,0,0);
    
    cout << temp_rating << "\n";
    fout << temp_rating << "\n";
}
    return 0;   
}