#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;
 
#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back 
#define pii pair<int,int>
#define mp make_pair
#define pi 3.14159265359
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int dp[1500][1500];
int v[1500],w[1500];
int h;
int n;

int solve(int i,int j){
  if(dp[i][j] != -1) return dp[i][j];

  int hoge;

  if(i == n) hoge = 0;

  else if(j < w[i]) hoge = solve(i+1, j);

  else hoge =  max(solve(i+1, j) , solve(i+1 , j - w[i]) + v[i]);

  return dp[i][j] = hoge;

}

int main(){

  while(1){
	cin >> h;
	if(h == 0) break;

	cin >> n;

	REP(i,n){
	  cin >> v[i]>> w[i];
	}

	REP(i,1500) REP(j,1500) dp[i][j] = -1;

	cout << solve(0,h) << endl;

  }
}