#include<bits/stdc++.h>
using namespace std;
//#define mx 1000
//int price[mx],weight[mx],dp[mx][mx];
int knapSack(int wt[], int val[], int n, int W)
{
int *dpPrev, *dpCurr, *tmp;
dpPrev = new int[W+1];
dpCurr = new int[W+1];
for(int i=0; i<=n; i++)
{
for(int m=0; m<= W; m++)
{
if (i==0 || m==0) dpCurr[m] = 0;
else if (wt[i-1] <= m) dpCurr[m] = max(val[i-1] + dpPrev[m-wt[i-1]], dpPrev[m]);
else dpCurr[m] = dpPrev[m];
}
tmp = dpPrev;
dpPrev = dpCurr;
dpCurr = tmp;
}
return dpPrev[W];
}
int main()
{
int n,W,*va,*wt;
cin>>W>>n;
va = new int[n];
wt = new int[n];
for(int i=0;i<n;i++) cin>>va[i]>>wt[i];
cout<<knapSack(wt, va, n, W)<<endl;
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKLy8jZGVmaW5lIG14IDEwMDAKLy9pbnQgcHJpY2VbbXhdLHdlaWdodFtteF0sZHBbbXhdW214XTsKCmludCBrbmFwU2FjayhpbnQgd3RbXSwgaW50IHZhbFtdLCBpbnQgbiwgaW50IFcpCnsKICAgIGludCAqZHBQcmV2LCAqZHBDdXJyLCAqdG1wOwogICAgZHBQcmV2ID0gbmV3IGludFtXKzFdOwogICAgZHBDdXJyID0gbmV3IGludFtXKzFdOwoKICAgIGZvcihpbnQgaT0wOyBpPD1uOyBpKyspCiAgICB7CiAgICAgICAgZm9yKGludCBtPTA7IG08PSBXOyBtKyspCiAgICAgICAgewogICAgICAgICAgICBpZiAoaT09MCB8fCBtPT0wKSAgICAgICAgZHBDdXJyW21dID0gMDsKCiAgICAgICAgICAgIGVsc2UgaWYgKHd0W2ktMV0gPD0gbSkgICBkcEN1cnJbbV0gPSBtYXgodmFsW2ktMV0gKyBkcFByZXZbbS13dFtpLTFdXSwgIGRwUHJldlttXSk7CgogICAgICAgICAgICBlbHNlICAgICAgICAgICAgICAgICAgICAgZHBDdXJyW21dID0gZHBQcmV2W21dOwogICAgICAgIH0KICAgICAgICAKICAgICAgICB0bXAgPSBkcFByZXY7CiAgICAgICAgZHBQcmV2ID0gZHBDdXJyOwogICAgICAgIGRwQ3VyciA9IHRtcDsKICAgIH0KICAgIAogICAgcmV0dXJuIGRwUHJldltXXTsKfQoKCmludCBtYWluKCkKewogICAgaW50IG4sVywqdmEsKnd0OwoKICAgIGNpbj4+Vz4+bjsKCiAgICB2YSA9IG5ldyBpbnRbbl07CgogICAgd3QgPSBuZXcgaW50W25dOwoKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspICAgY2luPj52YVtpXT4+d3RbaV07CgogICAgY291dDw8a25hcFNhY2sod3QsIHZhLCBuLCBXKTw8ZW5kbDsKCgogICAgcmV0dXJuIDA7Cn0=