#include <fstream>
using namespace std;

ifstream f( "date.in" );
ofstream g( "date.out" );

/*
Avem un rucsac de capacitate C (poate transporta C kg, nu conteaza volumul).
     m categorii de obiecte, distincte, date prin greutate si valoare (pot pune in rucsac de mai multe ori acelasi obiect)
Un hot intra intr-o casa si vrea sa maximizeze valoarea obiectelor furate. Care este valoarea maxima pe care o obtine?
*/

const int N = 2022; /// valoarea maxima capacitatii de transport
const int M = 20; /// numarul maxim de categorii de obiecte

int n, m;
int dp[ N ][ M ]; /// dp[x][y] = val maxima furata intr-un rucsac de capacit x, folosind categoriile de obiecte 1, 2, ..., y
                  /// practic fiecare rand rezolva pentru o capacitate a rucsacului fixa folosind sau primul obiect, sau primele 2 obiecte, ....
int val[ M ], gr[ M ];/// valorile si greutatile obiectelor

/**    Partea esentiala
       Linia = capacitatea rucsacului = subproblema pentru care rezolv
       Totul tine de explorarea: IAU / NU IAU un obiect
       Sa zicem ca vreau sa completez dp[i][j]. Inseamna ca am completat toate liniile de la 1 la i - 1 folosindu-ne de toate coloanele
       Am capacitatea i, a rucsacului. Vreau sa vad daca adaug sau nu categoria j. Pot gandi asa:
              1) NU adaug obiectul din categoria j. Ma voi folosi de cele anterioare.
              2) FOLOSESC categoria j. Asta inseamna ca ma pot uita la un rucsac umplut pana la capacitatea i - gr[ j ], care contine o combinatie a j - 1 categorii de obiecte si,
                 la suma de acolo, adaug valoarea obiectului din categoria j
       Pe dp[ i ][ j ] pastrez cea mai mare suma dintre cele doua situatii, comparand cu valoarea de dinainte
**/

/// Fiecare obiect este luat o singura data
void rucsac_clasic_obiect_unic()
{
    int i, j, folosesc_obiectul_j, nu_folosesc_obiectul_j;
    for( i = 1; i <= n; ++i )
        for( j = 1; j <= m; ++j )
        {
            folosesc_obiectul_j = nu_folosesc_obiectul_j = 0;

            if( i - gr[ j ] >= 0 ) /// daca greutatea obiectului din categoria j NU depaseste capacitatea rucsacului
                folosesc_obiectul_j = dp[ i - gr[j] ][ j - 1 ] + val[ j ];

            nu_folosesc_obiectul_j = dp[ i ][ j - 1 ];

            dp[ i ][ j ] = max( dp[ i ][ j ], max( folosesc_obiectul_j, nu_folosesc_obiectul_j ) );
        }

}

/// Pot folosi un obiect dintr-o categorie oarecare, de cate ori am nevoie
/// Asta inseamna ca voi continua sa pun, pastrand intotdeauna maximul
int dp_multiplu[ N ];
void rucsac_clasic_obiect_multiplu()
{
    int i, j;
    for( i = 1; i <= n; ++i )
        for( j = 1; j <= m; ++j )
            {
                int gr_anterioara = i - gr[ j ];
                if( gr_anterioara >= 0 )
                    dp_multiplu[ i ] = max( dp_multiplu[ i ], dp_multiplu[ gr_anterioara ]  +  val[ j ] );
            }

}


void afiseaza_matricea()
{
    int i, j;
    g << "Capacitatea rucsacului: " << n << endl;
    g << "Valoare:   ";
    for( i = 1; i <= m; ++i )
        g << val[ i ] << "  ";
    g << endl << "Greutate:   ";
    for( i = 1; i <= m; ++i )
        g << gr[ i ] << "  ";
    g << endl << endl;
    for( i = 1; i <= n; ++i )
        {
            g << "Rucsac de capacit  " << i << "   : ";
            for( j = 1; j <= m; ++j )
                g << dp[ i ][ j ] << "  ";
            g << endl;
        }
    g << endl << endl;
}


/// Ca sa gasesc obiectele pe care le-am folosit, plec de la cea mai mare suma, ma deplasez cat de mult pot in stanga, pe linie. Asa aflu prima data cand l-am pus.
/// Apoi, primul nr diferit de max il caut pe randurile de deasupra. Urc cat de mult pot, apoi ma deplasez la stanga
void afiseaza_solutia()
{
    int maxim = dp[ n ][ m ], lin = n, col = m;
    g << "Obiectele alese in ordinea inversa a introducerii: "<< endl;
    while( lin > 0  &&  col > 0 )
        {
            if( dp[ lin ][ col ]  !=  dp[ lin ][ col - 1 ] )
                {
                    g << "Am folosit obiectul nr " << col << ", de valoare " << val[ col ] << " si greutate " << gr[ col ] << endl;
                    lin = lin - gr[ col ];
                }
            --col;
        }
    g << endl;
}

void afiseaza_vct()
{
    for( int i = 1; i <= n; ++i )
        {
            g << "Rucsac de capacit  " << i << "   : ";
            g << dp_multiplu[ i ] << "  " << endl;
        }
    g << endl << endl;
}

int main()
{
    int i;

    f >> n >> m;
    for(i = 1; i <= m; ++i )
        f >> val[ i ] >> gr[ i ];


    rucsac_clasic_obiect_unic();
    afiseaza_matricea();
    g << "Obiecte unice: Suma maxima care se obtine este " << dp[ n ][ m ] << endl << endl;
    afiseaza_solutia();

    rucsac_clasic_obiect_multiplu();
    afiseaza_vct();
    g << "Obiecte nelimitate: Suma maxima care se obtine este " << dp_multiplu[ n ] << endl << endl;

    return 0;
}