// Sonny's solution to change
// Stanford Local Programming Contest, October 2007

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct coin
{
    int v, n;
    coin(int x = 0, int y = 0) : v(x), n(y) {}
};

istream &operator>>(istream &stream, coin &c)
{
    stream >> c.v >> c.n;
    return stream;
}

bool operator<(const coin &a, const coin &b)
{
    return a.v < b.v;
}

int main()
{
    int C, m;
    while (cin >> C >> m)
    {
        if (C == 0) break;
        
        // read the coins
        vector<coin> c(m);
        for (int i = 0; i < m; ++i)
            cin >> c[i];
            
        // sort the coins
        sort(c.begin(), c.end());
        
        // make sure we can start
        int coins = 0, value = 0;
        bool going = (c[0].v == 1);

        // go forward through our coins
        int i;
        for (i = 0; going && (i < m-1); ++i)
        {
            while (value+1 < c[i+1].v)
            {
                // grab a coin
                if (c[i].n) {
                    value += c[i].v;
                    --c[i].n;
                    ++coins;
                }
                else {
                    going = false;
                    break;
                }
                
                // check for termination
                if (value >= C) {
                    going = false;
                    break;
                }
            }
        }
        
        // go backward through the coins now
        for (; going && (i >= 0); --i)
        {
            while (c[i].n)
            {
                // grab another coin
                value += c[i].v;
                --c[i].n;
                ++coins;
                
                // check for termination
                if (value >= C) {
                    going = false;
                    break;
                }                
            }
        }
       
        // print result
        if (value >= C) cout << coins << endl;
        else            cout << "Not possible" << endl;
    }

    return 0;
}