#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> m >> n;
    vector<int> P(m + 1, 0);
    // V Q máme dvojice (nejvyšší cena, číslo zduplikovaného modelu)
    vector<pair<int, int>> Q(m + 1, make_pair(0, 0));
    for (int i = 0; i < n; ++i) {
        int w, c;
        cin >> w >> c;
        for (int j = m; j >= w; --j) {
            if (P[j-w] + c > P[j])
                P[j] = P[j-w] + c;
            if (Q[j-w].first + c > Q[j].first)
                Q[j] = make_pair(Q[j-w].first + c, Q[j-w].second);
            if (j >= 2*w && P[j-2*w] + 2*c > Q[j].first)
                Q[j] = make_pair(P[j-2*w] + 2*c, i+1);
        }
    }

    if (Q[m].first > P[m])
        cout << "zduplikuj model " << Q[m].second << endl
             << "nejlepsi cena " << Q[m].first << endl;
    else
        cout << "nezduplikuj nic" << endl
             << "nejlepsi cena " << P[m] << endl;
    return 0;
}