// In the name of Allah the Lord of the Worlds.
 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll m , n;
 
vector<int>v1 , v2;
 
ll dp[10205][105][2];
 
ll f(int w , int i , int b)
{
 
    if(w>m+200){
 
        return -1e9;
    }
 
    if(i==n){
 
        if(w>2000){
 
            if(w<=m+200)return 0;
        }
 
        else if(w<=m)return 0;
 
        return -1e9;
    }
 
 
    ll value = 0;
 
    value = f(w+v1[i] , i+1 , b) + v2[i];
 
    value = max(value , f(w , i+1 , b));
 
    return dp[w][i][b] = value;
}
 
int main(void)
{
    while(scanf("%lld %lld",&m , &n)==2){
 
        v1.clear() , v2.clear();
 
        memset(dp , -1 , sizeof(dp));
 
        for(int i=0;i<n;i++){
 
            int in1 , in2;
            scanf("%d %d",&in1,&in2);
            v1.push_back(in1);
            v2.push_back(in2);
        }
 
        printf("%lld\n",f(0 , 0 , 0));
    }
    return 0;
}
 

Ly8gSW4gdGhlIG5hbWUgb2YgQWxsYWggdGhlIExvcmQgb2YgdGhlIFdvcmxkcy4KCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKCmxsIG0gLCBuOwoKdmVjdG9yPGludD52MSAsIHYyOwoKbGwgZHBbMTAyMDVdWzEwNV1bMl07CgpsbCBmKGludCB3ICwgaW50IGkgLCBpbnQgYikKewoKICAgIGlmKHc+bSsyMDApewoKICAgICAgICByZXR1cm4gLTFlOTsKICAgIH0KCiAgICBpZihpPT1uKXsKCiAgICAgICAgaWYodz4yMDAwKXsKCiAgICAgICAgICAgIGlmKHc8PW0rMjAwKXJldHVybiAwOwogICAgICAgIH0KCiAgICAgICAgZWxzZSBpZih3PD1tKXJldHVybiAwOwoKICAgICAgICByZXR1cm4gLTFlOTsKICAgIH0KCgogICAgbGwgdmFsdWUgPSAwOwoKICAgIHZhbHVlID0gZih3K3YxW2ldICwgaSsxICwgYikgKyB2MltpXTsKCiAgICB2YWx1ZSA9IG1heCh2YWx1ZSAsIGYodyAsIGkrMSAsIGIpKTsKCiAgICByZXR1cm4gZHBbd11baV1bYl0gPSB2YWx1ZTsKfQoKaW50IG1haW4odm9pZCkKewogICAgd2hpbGUoc2NhbmYoIiVsbGQgJWxsZCIsJm0gLCAmbik9PTIpewoKICAgICAgICB2MS5jbGVhcigpICwgdjIuY2xlYXIoKTsKCiAgICAgICAgbWVtc2V0KGRwICwgLTEgLCBzaXplb2YoZHApKTsKCiAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKyl7CgogICAgICAgICAgICBpbnQgaW4xICwgaW4yOwogICAgICAgICAgICBzY2FuZigiJWQgJWQiLCZpbjEsJmluMik7CiAgICAgICAgICAgIHYxLnB1c2hfYmFjayhpbjEpOwogICAgICAgICAgICB2Mi5wdXNoX2JhY2soaW4yKTsKICAgICAgICB9CgogICAgICAgIHByaW50ZigiJWxsZFxuIixmKDAgLCAwICwgMCkpOwogICAgfQogICAgcmV0dXJuIDA7Cn0K

MTk4MSA3NQozMTk5IDQKMjYgNQoxMTE0IDEKMTIwMyAxCjIzNDEgMgoyMjU1IDUKODI0IDEKNDY1IDEKNDg1IDEKMjk3NyAyCjI0MzEgNQoyMTk3IDMKMTY2NSAyCjk0MCAxCjM2MTkgMgoyNDI3IDMKMjI2OSAyCjEzNzQgNAoyODI1IDIKMjk4NCAyCjI1NTggMgoyNDIyIDUKMTYzNSAxCjE0OTMgMwozNyAyCjM5MTggMQoyMjY5IDIKMzQ3MCA0CjI2ODYgMwoxMjgxIDEKMjE0NCA0CjE0NzIgMgoyODYzIDIKMzc5NCA1CjE3NzMgMgozNTU1IDQKMTA3MCA1CjYzIDEKMTIxMyA1CjE1MjggMgoyNzI4IDEKNjcgNQozOTEwIDMKMTYzMiAzCjY0OSA1Cjg5OCAzCjI5NzEgNAozNTU1IDEKMTkxNyA1CjM4NzEgNQozMTgwIDUKMzcxIDIKMTc1MiA1CjMzMDYgMwoyMzQwIDIKOTE3IDMKMjYyOSA0CjMxMTggMQoxNTc1IDMKMTQ4NCA0CjEzIDUKMTcxOCAxCjE0NTMgMQoxNTIwIDUKMTY3NiA0CjM0MTAgMwoxNTE5IDEKMTEwNSAxCjIxMyAzCjI5MzkgMgoxOTQ2IDQKNjc0IDIKMTg5NCA0CjM0NjMgMQo1NDAgMQ==

1981 75
3199 4
26 5
1114 1
1203 1
2341 2
2255 5
824 1
465 1
485 1
2977 2
2431 5
2197 3
1665 2
940 1
3619 2
2427 3
2269 2
1374 4
2825 2
2984 2
2558 2
2422 5
1635 1
1493 3
37 2
3918 1
2269 2
3470 4
2686 3
1281 1
2144 4
1472 2
2863 2
3794 5
1773 2
3555 4
1070 5
63 1
1213 5
1528 2
2728 1
67 5
3910 3
1632 3
649 5
898 3
2971 4
3555 1
1917 5
3871 5
3180 5
371 2
1752 5
3306 3
2340 2
917 3
2629 4
3118 1
1575 3
1484 4
13 5
1718 1
1453 1
1520 5
1676 4
3410 3
1519 1
1105 1
213 3
2939 2
1946 4
674 2
1894 4
3463 1
540 1