# Appreciation

/*
 * Problem :: 2624 / 동전 바꿔주기
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 전형적인 DP 문제인데...
 *   사용할 수 있는 동전의 개수가 제한되어있다
 *   그동안은 딱 1개만 사용할 수 있거나 무한으로 사용할 수 있는 경우만 다루었는데...
 *   + dp[i][j] = 1~i 번째 동전까지 적절히 사용해서 j 원을 만드는 경우의 수
 *     # 1개인 경우
 *       for (int i=1; i<=K; i++)
 *           for (int j=0; j<=T; j++) {
 *               dp[i][j] = dp[i-1][j]; <= i 번째 동전 사용하지 않은 경우
 *               if (j-P[i]) {
 *                   dp[i][j] += dp[i-1][j-P[i]]; <= i 번째 동전 사용한 경우
 *               }
 *           }
 *     # 무한개인 경우
 *       for (int i=1; i<=K; i++)
 *           for (int j=0; j<=T; j++) {
 *               dp[i][j] = dp[i-1][j]; <= i 번째 동전 사용하지 않은 경우
 *               if (j-P[i]) {
 *                   dp[i][j] += dp[i][j-P[i]]; <= i 번째 동전 사용한 경우
 *               }
 *           }
 *     -> 사실 무한개의 경우에서
 *        if (j-P[i]) {
 *            dp[i][j] += dp[i][j-P[i]];
 *        }
 *        는
 *        for (int k=1; k*P[i]<=T; k++) {
 *            dp[i][j] += dp[i-1][T-k*P[i]];
 *        }
 *        와 같다
 *        => 현재 dp[3][20] 을 구해야 하고 P[3] = 5 라고 하자
 *           dp[3][20] = dp[2][20]   - 현재 5원 동전 사용 안함
 *                       + dp[2][15] - 현재 5원 동전 1개 사용함
 *                       + dp[2][10] - 현재 5원 동전 2개 사용함
 *                       + dp[2][5]  - 현재 5원 동전 3개 사용함
 *                       + dp[2][0]  - 현재 5원 동전 4개 사용함
 *           이때 dp[3][15] 를 살펴보자
 *           dp[3][15] = dp[2][15]   - 현재 5원 동전 사용 안함
 *                       + dp[2][10] - 현재 5원 동전 1개 사용함
 *                       + dp[2][5]  - 현재 5원 동전 2개 사용함
 *                       + dp[2][0]  - 현재 5원 동전 3개 사용함
 *           여기서
 *           dp[3][20] 의 5원 동전을 적어도 하나 이상 사용한 경우는
 *           dp[3][15] 의 각 경우에 5원 동전을 추가로 사용한 경우와 같다!
 *           (실제로 식을 보면 dp[3][20] = dp[2][20] + dp[3][15] 와 같음을 확인할 수 있다!)
 *
 * - 그래서... 결국 말하고자 하는 바는
 *   우리는 동전이 무한하지 않아서
 *   동전의 개수를 고려하는 for 문을 추가해야한다는 것이다
 *   + 위에서 만약 5원 동전이 3개밖에 없다면...
 *     dp[3][20] = dp[2][20]
 *                 + dp[2][15]
 *                 + dp[2][10]
 *                 + dp[2][5]
 *     여야 되기 때문이다... <= dp[2][0] 은 동전을 4개 사용해야함
 *     # 위와 같은 논의에 따르면 점화식은 다음과 같다
 *       for (int i=1; i<=K; i++)
 *           for (int j=0; j<=T; j++) {
 *               for (int k=0; k<=N[i]; k++) {
 *                   if (j-k*P[i] >= 0) {
 *                       dp[i][j] += dp[i-1][j-k*P[i]];
 *                   }
 *               }
 *           }
 *
 * Point
 * - 근데 O(T*K*N) 이면 O(10^9) 인데 시간초과 아닌가?
 *   + 그런데 32ms 로 통과했다...?
 *     # 다른 사람들은 0ms 통과한 사람도 있길래 보았더니
 *       j 를 0~T 가 아닌 T~0 으로 순회했다
 *       -> k*P[i] 가 j 보다 큰 경우 만들 수 있는 방법이 없기 때문에
 *          break 를 통해 for 문을 바로 종료시켜주는 좋은 최적화이다
 *
 * - DP 과정에서 각 dp 마다
 *   dp[i][j] = dp[i-1][j]
 *   가 수행된다
 *   + 때문에 dp[i] 으로 공간복잡도를 줄일 수 있다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int T; cin >> T;
    int K; cin >> K;
    int P[K+1], N[K+1];
    for (int i=1; i<=K; i++)
        cin >> P[i] >> N[i];

    // Process
    int dp[K+1][T+1];
    memset(dp, 0, sizeof(dp));

    dp[0][0] = 1;
    for (int i=1; i<=K; i++) {
        for (int j=T; j>=0; j--) {
            for (int k=0; k<=N[i]; k++) {
                if (j-k*P[i] >= 0) {
                    dp[i][j] += dp[i-1][j-k*P[i]];
                } else break;
            }
        }
    }

    // dp[0][0] = 1;
    // for (int i=1; i<=K; i++) {
    //     for (int j=0; j<=T; j++) {
    //         for (int k=0; k<=N[i]; k++) {
    //             if (j-k*P[i] >= 0) {
    //                 dp[i][j] += dp[i-1][j-k*P[i]];
    //             }
    //         }
    //     }
    // }

    // Control : Output
    cout << dp[K][T] << endl;
}

// Helper Functions
/* None */