#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

int max(int a, int b) { return (a > b) ? a : b; }

bool isIntNumb(string s) {
    return s.find_first_not_of("0123456789") == string::npos;
}

int NOD(int x, int y)
{
    return !y ? x : NOD(y, x % y);
}

int NOD(vector<int> numbers)
{
    if (numbers.empty())
        return 1;

    if (numbers.size() == 1)
        return numbers[0];

    int res = numbers[0];

    for (int i = 1; i < numbers.size(); i++)
        res = NOD(res, numbers[i]);

    return res;
}

vector<int> Solve(vector<int> weight, vector<int> cost, int& maxC, int& maxW, int w)
{
    int nod = NOD(NOD(weight), w);
    w /= nod;
    for (int i = 0; i < weight.size(); i++)
        weight[i] /= nod;

    int maxWeight = 0;

    for (int i = 0; i < weight.size(); ++i)
        maxWeight += weight[i];
    if (w < maxWeight)
        maxWeight = w;

    int width = maxWeight + 1;
    int height = cost.size() + 1;

    vector<vector<int>> matrix(height, vector<int>(width));
    for (int i = 0; i < height; ++i)
        matrix[i][0] = 0;
    for (int i = 0; i < width; ++i)
        matrix[0][i] = 0;


    for (int i = 0; i < height - 1; ++i)
        for (int j = 0; j < width; ++j)
            if (j >= weight[i])
            {
                if (matrix[i][j] > matrix[i][j - weight[i]] + cost[i])
                    matrix[i + 1][j] = matrix[i][j];
                else
                    matrix[i + 1][j] = matrix[i][j - weight[i]] + cost[i];
            }
            else
                matrix[i + 1][j] = matrix[i][j];

    vector<int> answer;
    int tempCost = matrix[height - 1][width - 1];
    int tempW = maxWeight;
    for (int i = height - 1; i > 0; --i)
        if (matrix[i][tempW] > matrix[i - 1][tempW]) {
            answer.push_back(i);
            maxC += cost[i - 1];
            maxW += weight[i - 1] * nod;
            tempCost -= cost[i - 1];
            tempW -= weight[i - 1];
        }

    return answer;
}

int main()
{
    int a, b, volume, errorsCount = 0;
    vector<string> input;
    string str, numb;
    getline(cin, str);
    stringstream in(str);
    while (in >> numb)
        input.push_back(numb);
    volume = stoi(input[0]);
    input.clear();
    vector<int> weight;
    vector<int> cost;
    while (!cin.fail()) {
        getline(cin, str);
        stringstream in(str);
        while (in >> numb)
            input.push_back(numb);
        if (input.size() == 0)
        {
            input.clear();
            continue;
        }
        else if (input.size() == 1 || input.size() > 2)
        {
            errorsCount++;
            input.clear();
            continue;
        }
        else if (!isIntNumb(input[0]) || !isIntNumb(input[1]))
        {
            errorsCount++;
            input.clear();
            continue;
        }
        a = stoi(input[0]);
        b = stoi(input[1]);
        input.clear();
        if (a >= 0 && b >= 0)
        {
            weight.push_back(a);
            cost.push_back(b);
        }
        else
            errorsCount++;
    }
    int maxW = 0;
    int maxC = 0;

    vector<int> matrix = Solve(weight, cost, maxC, maxW, volume);
    if (matrix.empty())
    {
        cout << "0 0" << endl;
        return 0;
    }

    for (int i = 0; i < errorsCount; ++i)
        cout << "error" << endl;
    cout << maxW << " " << maxC << endl;
    for (int i = matrix.size() - 1; i >= 0; --i) {
        cout << matrix[i] << endl;
    }
    return 0;
}