#include <iostream>
#include <cstring>
using namespace std;
#define int long long
const int MAX_T = 1e7 + 5;
int memo[MAX_T];          
int cost[10005], val[10005]; 
int m;                     

int dfs(int time) {
    if (time <= 0) return 0;
    if (memo[time] != -1) return memo[time];
    
    int max_val = 0;
    for (int i = 0; i < m; ++i) { // 遍历所有草药
        if (cost[i] <= time) {
            max_val = max(max_val, val[i] + dfs(time - cost[i]));
        }
    }
    memo[time] = max_val; // 记录结果
    return max_val;
}

signed main() {
    int t;
    cin >> t >> m;
    
 
    for (int i = 0; i < m; ++i) {
        cin >> cost[i] >> val[i];
    }
    
  
    memset(memo, -1, sizeof(memo));
    
    cout << dfs(t) << endl;
    return 0;
}