잔돈 만들기

수(Sue)는 식료품점에서 계산 줄에 서 있습니다. 급한 나머지 자기 차례가 되면 정확한 금액으로 지불하고 싶어 합니다. 그런데 물건들의 총액이 정확히 얼마인지는 아직 모르고, 다만 총액의 상한 $C$ 만 알고 있습니다.

수의 주머니에 든 동전들(각 액면가와 그 개수)이 주어질 때, $1$ 부터 $C$ 까지의 모든 금액에 대해 정확히 그 금액을 지불할 수 있도록 하려면 최소 몇 개의 동전을 미리 꺼내 두어야 하는지 구하세요.

여기서 "동전을 꺼내 둔다"는 것은 미리 동전 몇 개를 골라 둔다는 뜻이며, $1$ 이상 $C$ 이하의 각 금액마다 꺼내 둔 동전들 중 일부(부분집합)를 골라 그 합이 정확히 그 금액이 되도록 만들 수 있어야 합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스의 첫 줄에는 두 정수 $C$ 와 $m$ 이 주어집니다 ($1 \le C \le 10^9$, $1 \le m \le 1000$). $C$ 는 수가 거스름돈을 만들 수 있어야 하는 최대 금액이고, $m$ 은 수가 가진 서로 다른 동전 액면가의 수입니다.

이어지는 $m$ 개의 줄에는 각각 두 정수 $v_i$ 와 $n_i$ 가 주어집니다 ($1 \le v_i \le 1000$, $1 \le n_i \le 1000$). $v_i$ 는 $i$ 번째 액면가의 값이고, $n_i$ 는 수가 그 액면가의 동전을 몇 개 가지고 있는지를 나타냅니다.

입력의 끝은 $0$ 하나만 있는 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 한 줄에, $1$ 부터 $C$ 까지의 모든 금액에 대해 정확한 거스름돈을 만들 수 있도록 하기 위해 수가 꺼내 두어야 하는 최소 동전 개수를 출력합니다.

어떤 동전 조합으로도 모든 금액을 만들 수 없다면 대신 "Not possible" 을 출력합니다.