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

const int MAX_MONEY = 30010;
long long int max_profit[MAX_MONEY];

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int money, number_of_projects;
 int investment, profit;
 int i, project, act_money;
 long long int solution;

 cin >> money;
 cin >> number_of_projects;

 for (i=1; i<=MAX_MONEY; ++i)
    max_profit[i] = -1;

 for (project=1; project<=number_of_projects; ++project) {
    cin >> investment;
    cin >> profit;
    for (act_money=money-investment; act_money>=0; --act_money) {
       if (max_profit[act_money] == -1)
          continue;
       max_profit[act_money+investment] = max (max_profit[act_money+investment], max_profit[act_money]+profit);
    }
 }

 solution=0;
 for (i=0; i<=money; ++i)
    solution = max(solution,max_profit[i]);

 cout << solution;

 return 0;
}