#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int c, m;
  while ((cin >> c) && (c != 0) && (cin >> m)) {
    vector<pair<int, int> > coins(m);
    for (int i = 0; i < m; i++)
      cin >> coins[i].first >> coins[i].second;
    sort(coins.begin(), coins.end());

    int cnt = 0, reached = 0, last_pos = -1;
restart:;
    while (last_pos < m-1 && coins[last_pos+1].first <= reached+1)
      last_pos++;
    int cur_pos = last_pos;
    while (cur_pos >= 0 && reached < c) {
      if (coins[cur_pos].second == 0) {
        cur_pos--;
        continue;
      }
      reached += coins[cur_pos].first;
      coins[cur_pos].second--;
      cnt++;
      if (last_pos < m-1 && coins[last_pos+1].first <= reached+1)
        goto restart;
    }
    if (reached >= c)
      cout << cnt << endl;
    else
      cout << "Not possible" << endl;
  }
  return 0;
}