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

using namespace std;

int main() {
  while (1) {
    int C, m;
    cin >> C;
    if (C == 0) break;
    cin >> m;

    vector<pair<int,int> > coins;
    for (int i = 0; i < m; i++) {
      int v, n;
      cin >> v >> n;
      coins.push_back(make_pair(v,n));      
    }

    // sort coins in order of decreasing value

    sort(coins.begin(), coins.end());
    reverse(coins.begin(), coins.end());

    // candidates contains the coins that could be used next

    vector<pair<int,int> > candidates;
    int num_coins = 0;
    int highest = 0;
    bool no_solution = false;

    while (highest < C) {

      // add all coins which could be used to achieve highest+1

      while (coins.size() > 0 && coins.back().first <= highest+1) {
	candidates.push_back(coins.back());
	coins.pop_back();
      }
      
      if (candidates.size() == 0) {
	no_solution = true;
	break;
      } else {
	
	// use the largest coin available
	
	num_coins++;
	highest += candidates.back().first;
	candidates.back().second--;
	if (candidates.back().second == 0)
	  candidates.pop_back();
      }
    }
    
    if (no_solution)
      cout << "Not possible" << endl;
    else	
      cout << num_coins << endl;
  }
}