#include <stdio.h>
main()
{
    int c, m, v[1024], n[1024], tmp, largest, t, coin, amount, used[1024];
    while(true){
        scanf("%d", &c);
        if(c == 0)
            return 0;
        scanf("%d", &m);
        for(int i = 1; i <= m; i++)
            scanf("%d%d", &v[i], &n[i]);
        for(int i = 0; i < 1024; i++)
            used[i] = 0;
        for(int i = m - 1; i >=1; i--)
            for(int j = 1; j <= i; j++)
                if(v[j] > v[j+1]){
                    tmp = v[j];
                    v[j] = v[j+1];
                    v[j+1] = tmp;
                    tmp = n[j];
                    n[j] = n[j+1];
                    n[j+1] = tmp;
                }
        /*for(int i = 1; i <= m; i++)
            printf("%4d %4d\n", v[i], n[i]);*/
        largest = t = 0;
        while(t < m && v[t + 1] <= largest + 1){
            t++;
            largest+=v[t] * n[t];
        }
        if(largest < c)
            printf("Not possible\n");
        else{
            coin = amount = 0;
            for(int i = 1; i <= t - 1; i++){
                if(amount < c){
                    while(amount < c && used[i] < n[i] && amount < v[i+1] - 1){
                        used[i]++;
                        coin++;
                        amount+=v[i];
                    }
                }
            /*for(int j = 1; j <= m; j++)
                printf("%d %d %d\n", v[j], n[j], used[j]);
            printf("current amount: %d\n", amount);*/
            }
            if(amount < c){
                for(int i = t; i >= 1; i--){
                    if(amount < c){
                        while(amount < c && used[i] < n[i]){
                            used[i]++;
                            coin++;
                            amount+=v[i];
                        }
                    }
                }
            }
            /*for(int i = 1; i <= m; i++)
                printf("%d %d %d\n", v[i], n[i], used[i]);
            printf("%d ", amount);*/
            printf("%d\n", coin);
        }
    }
}