#include <iostream>
#include <iomanip>
//Wykonanie by Grzegorz Bogusław Zaleski
using namespace std;

/*
10 6
6 6
4 2
5 3
7 2
10 3
2 1
*/

int main()
{
    int udzwig, przedmioty;
    cin >> udzwig >> przedmioty;
    int Values[przedmioty+1];
    int Weights[przedmioty+1];
    for (int i=1; i<=przedmioty; ++i)
    {
        cin >> Values[i] >> Weights[i];
    }


    int Plecak[przedmioty+1][udzwig+1];
    int Input[przedmioty+1][udzwig+1];
    for (int i=0; i<=przedmioty; i++)
    {
        for (int j=0; j<=udzwig; ++j)
        {
            if (i == 0 or j == 0)
            {
                Plecak[i][j] = 0;
                Input[i][j] = 0;
            }

            else if (Weights[i] <= j)
            {
                Plecak[i][j] = max(Plecak[i-1][j-Weights[i]] + Values[i], Plecak[i-1][j]);
                Input[i][j] = 0;
                if (Plecak[i-1][j-Weights[i]] + Values[i] > Plecak[i-1][j]) Input[i][j] = 1;
            }
            else
            {
                Plecak[i][j] = Plecak[i-1][j];
                Input[i][j] = Input[i-1][j];
            }
        }
    }
    cout << "Max wartosc: " <<Plecak[przedmioty][udzwig] << endl;

    int countdown = udzwig;

    for (int i=przedmioty; i>-1; --i)
    {
        if (Input[i][countdown] == 1)
        {
            cout << "Wzieto przedmiot nr " << i << endl;
            countdown -= Weights[i];
        }
    }

    return 0;
}