#include <stdio.h>
#include <bits/stdc++.h>
//%lld
typedef long long ll;
using namespace std;
//Knapsack
int peso[2005];
int valor[2005];
int matriz[2005][2005];
int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int s, n;
    cin>>s>>n;
    for(int i = 0;i<n;i++){
        cin>>peso[i]>>valor[i];
    }
    for(int i = peso[0];i<=s;i++){
        matriz[0][i] = valor[0];
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=s;j++){
            if(peso[i]>j){
                matriz[i][j] = matriz[i-1][j];
            }else{
                matriz[i][j] = max((valor[i]+matriz[i-1][j-peso[i]]), matriz[i-1][j]);
            }
        }
    }
    int saida = 0;
    for(int i = 0;i<=s;i++){
        if(matriz[i][s]>saida)saida = matriz[i][s];
    }
    cout<<saida<<"\n";
}