동전 바꿔주기

가게의 현금 출납기에는 k가지 동전이 있다. i번째 동전 종류는 한 개의 금액이 p_i이고, 모두 n_i개 있다.

가게 주인은 금액이 T원인 지폐 한 장을 이 동전들로 바꾸려고 한다. 각 동전 종류는 가지고 있는 개수 이하로만 사용할 수 있으며, 각 종류의 동전을 몇 개씩 쓰는지가 같다면 순서와 관계없이 같은 방법으로 센다.

T, k, 그리고 각 동전 종류의 금액 p_i와 개수 n_i가 주어질 때, 정확히 T원이 되도록 지폐를 동전으로 바꾸는 방법의 수를 구하라. 방법의 수는 2^31 - 1을 넘지 않는다고 가정한다.

첫째 줄에 지폐의 금액 T가 주어진다. 0 < T <= 10,000이다.

둘째 줄에 동전 종류의 수 k가 주어진다. 0 < k <= 100이다.

셋째 줄부터 k개의 줄에는 각 동전 종류의 금액 p_i와 개수 n_i가 공백 하나로 구분되어 주어진다. 0 < p_i <= T, 0 < n_i <= 1,000이다.

첫째 줄에 동전으로 T원을 만드는 방법의 수를 출력한다. 방법이 없으면 0을 출력한다.