#include<bits/stdc++.h>
using namespace std;
int dp[20005];
int main(){
    int n,maxw;scanf("%d%d",&maxw,&n);
    while(n--){
        int v,w;scanf("%d%d",&v,&w);
        for(int i=maxw;i>=v;i--) dp[i]=max(dp[i-v]+w,dp[i]);
    }
    printf("%d",dp[maxw]);
    return 0;
}
/**************************************************************
	Problem: 1282
	User: wangyichen2
	Language: C++
	Result: Accepted
	Time:52 ms
	Memory:2156 kb
****************************************************************/