import java.util.*;

public class change {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while (true) {
			int c = s.nextInt();
			if (c == 0) break;
			int m = s.nextInt();
			int[] array = new int[m];
			for (int i = 0; i < m; i++) {
				array[i] = s.nextInt() << 16;
				array[i] |= s.nextInt();
			}
			Arrays.sort(array);
			int soFar = 0;
			int count = 0;
			int maxIndex = 0;
			while (soFar < c) {
				while (maxIndex < m && ((array[maxIndex] >> 16) <= soFar + 1)) maxIndex++;
				maxIndex--;
				int index = maxIndex;
				while (index >= 0 && (array[index] & ((1 << 16) - 1)) == 0) index--;
				if (index == -1) break;
				array[index]--;
				count++;
				soFar += array[index] >> 16;
			}
			if (soFar < c) System.out.println("Not possible");
			else System.out.println(count);
		}
	}
}