명보네 동네 가게의 현금 출납기에는 k 가지의 동전이 각각 n₁, n₂ , .. ,n_k 개씩 들어있다. 가게주인은 명보에게 T 원의 지폐를 동전으로바꿔 주려고 한다. 이때 , 동전 교환 방법은 여러가지가 있을 수 있다.

예를 들어 , 10 원 짜리, 5 원짜리, 1 원짜리 동전이 각각 2 개,3 개, 5 개씩 있을 때, 20 원짜리 지폐를 다음과 같은 방법으로 교환할 수 있다.

20=10 * 2
20=10 * 1 + 5 * 2
20=10 * 1 + 5 * 1 + 1 * 5
20= 5 * 3 + 1 * 5

입력으로 지폐의 금액 T , 동전의 가지수 k , 각 동전 하나의금액 p_i 와 n_i가 주어질 때 (i= 1, 2, ... k) 지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오. 단 , 방법의 가지 수는 2³¹을 초과하지 않는 것으로 한다.

입력 방법

• 첫째 줄에는 지폐의 금액 T ( 0 < T <= 10,000),
• 둘째 줄에는 동전의 가짓수 k ( 0 < k <= 100),
• 셋째 줄부터 마지막 줄까지는 각 줄에 동전의 금액 p_i( 0 < p_i <= T) 와 개수 n_i( 0 < n_i <= 1,000)가 주어진다. p_i 와 n_i 사이에는 빈칸이 하나씩 있다.

출력 방법

입력과 출력의 예

입력

20
3
5 3
10 2
1 5

출력

4

출처:koi 중등 기출