#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  int max,n,num[1001],a[1001],used,left,i,j,C;
  while(1){
    scanf("%d",&C);
    if (!C) break;
    scanf("%d",&n);
    left=0;
    for(i=0;i<n;i++){
      scanf("%d%d",&a[i],&num[i]);
      left+=num[i];
    }
    for(i=0;i<n;i++){
      for(j=i+1;j<n;j++) if (a[i]>a[j]){
        swap(a[i],a[j]);
        swap(num[i],num[j]);
      }
    }
    max=0;
    used=0;
    int p=n-1;
    while(1){
      if (max>=C){
        printf("%d\n",used);
        break;
      }
      if (left==0){
        printf("Not possible\n");
        break;
      }
      /*
      if (max>=1000){
        while(p>=0 && num[p]==0) p--;
        if (p<0){
          printf("Not possible\n");
          break;
        }
        num[p]--;
        max+=a[p];
        used++;
        left--;
      }
      else{
      */
        for(i=n-1;i>=0;i--){
          if (a[i]<=max+1 && num[i]){
            break;
          }
        }
        if (i<0){
          printf("Not possible\n");
          break;
        }else{
          num[i]--;
          max+=a[i];
          left--;
          used++;
        }
//      }
    }
  }
  return  0;
}