#include<bits/stdc++.h>
using namespace std;
//#define mx 1000
//int price[mx],weight[mx],dp[mx][mx];
int max_n = 500, max_W = 2000000;
long long knapSack(int wt[], int val[], int n, int W)
{
long long *dpPrev, *dpCurr, *tmp;
dpPrev = new long long[max_W+1];
dpCurr = new long long[max_W+1];
int c = 0;
for(int i=0; i<=max_n; i++)
{
for(int m=0; m<=max_W; m++)
{
c++;
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;
}
cout<<c<<endl;
return dpPrev[W];
}
int main()
{
int n,W,*va,*wt;
cin>>W>>n;
va = new int[max_n];
wt = new int[max_n];
for(int i=0;i<n;i++) cin>>va[i]>>wt[i];
for(int i=n;i<max_n;i++){
va[i] = i;
wt[i] = 2*i;
}
cout<<knapSack(wt, va, n, W)<<endl;
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKLy8jZGVmaW5lIG14IDEwMDAKLy9pbnQgcHJpY2VbbXhdLHdlaWdodFtteF0sZHBbbXhdW214XTsKCmludCBtYXhfbiA9IDUwMCwgbWF4X1cgPSAyMDAwMDAwOwoKbG9uZyBsb25nIGtuYXBTYWNrKGludCB3dFtdLCBpbnQgdmFsW10sIGludCBuLCBpbnQgVykKewogICAgbG9uZyBsb25nICpkcFByZXYsICpkcEN1cnIsICp0bXA7CiAgICBkcFByZXYgPSBuZXcgbG9uZyBsb25nW21heF9XKzFdOwogICAgZHBDdXJyID0gbmV3IGxvbmcgbG9uZ1ttYXhfVysxXTsKICAgIAogICAgaW50IGMgPSAwOwoKICAgIGZvcihpbnQgaT0wOyBpPD1tYXhfbjsgaSsrKQogICAgewogICAgICAgIGZvcihpbnQgbT0wOyBtPD1tYXhfVzsgbSsrKQogICAgICAgIHsKICAgICAgICAJYysrOwogICAgICAgICAgICBpZiAoaT09MCB8fCBtPT0wKSAgICAgICAgZHBDdXJyW21dID0gMDsKCiAgICAgICAgICAgIGVsc2UgaWYgKHd0W2ktMV0gPD0gbSkgICBkcEN1cnJbbV0gPSBtYXgodmFsW2ktMV0gKyBkcFByZXZbbS13dFtpLTFdXSwgIGRwUHJldlttXSk7CgogICAgICAgICAgICBlbHNlICAgICAgICAgICAgICAgICAgICAgZHBDdXJyW21dID0gZHBQcmV2W21dOwogICAgICAgIH0KICAgICAgICAKICAgICAgICB0bXAgPSBkcFByZXY7CiAgICAgICAgZHBQcmV2ID0gZHBDdXJyOwogICAgICAgIGRwQ3VyciA9IHRtcDsKICAgIH0KICAgIAogICAgY291dDw8Yzw8ZW5kbDsKICAgIHJldHVybiBkcFByZXZbV107Cn0KCgppbnQgbWFpbigpCnsKICAgIGludCBuLFcsKnZhLCp3dDsKCiAgICBjaW4+Plc+Pm47CgogICAgdmEgPSBuZXcgaW50W21heF9uXTsKCiAgICB3dCA9IG5ldyBpbnRbbWF4X25dOwoKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspICAgY2luPj52YVtpXT4+d3RbaV07CgogICAgZm9yKGludCBpPW47aTxtYXhfbjtpKyspewogICAgICAgIHZhW2ldID0gaTsKICAgICAgICB3dFtpXSA9IDIqaTsKICAgIH0KCiAgICBjb3V0PDxrbmFwU2Fjayh3dCwgdmEsIG4sIFcpPDxlbmRsOwoKICAgIHJldHVybiAwOwp9