#include<bits/stdc++.h>
using namespace std;

int w[101], v[101];    // 存储物品信息：w[i]表示第i件物品的重量，v[i]表示第i件物品的价值
int dp[22001];         // 动态规划数组：dp[j]表示背包容量为j时能获得的最大价值

int main() {
    int t, m;          // t:背包总容量(M), m:物品数量(N)
        cin >> t >> m;     // 输入背包容量和物品数量
            
                // 循环读取每件物品的重量和价值
                    for (int i = 1; i <= m; i++) {
                            cin >> w[i] >> v[i];  // 输入第i件物品的重量w[i]和价值v[i]
                                }
                                    
                                        // 动态规划求解01背包问题
                                            for (int i = 1; i <= m; i++) {           // 遍历每件物品
                                                    // 逆序遍历背包容量（从大到小更新，避免重复放入）
                                                            for (int j = t; j >= w[i]; j--) {    // j从背包总容量t递减到当前物品重量w[i]
                                                                        // 状态转移：比较放入当前物品和不放当前物品的价值
                                                                                    // 1. 放入：dp[j-w[i]]（剩余空间的最大价值） + v[i]（当前物品价值）
                                                                                                // 2. 不放入：保持原来的dp[j]
                                                                                                            dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
                                                                                                                    }
                                                                                                                        }
                                                                                                                            
                                                                                                                                // 输出背包容量为t时的最大价值
                                                                                                                                    cout << dp[t];
                                                                                                                                        return 0;
                                                                                                                                        }