#include<bits/stdc++.h>

using namespace std;

int n,m;

int w[20001],v[20001],a[20001];

int main(){

cin>>m>>n;

for(int i=1;i<=n;i++) cin>>w[i]>>v[i];

for(int i=1;i<=n;i++){

	for(int j=m;j>=w[i];j--){

		a[j]=max(a[j],a[j-w[i]]+v[i]);

	}

}

cout<<a[m];

}