#include<bits/stdc++.h> using namespace std; int f[397][397],n,m,c[510],w[510]; int main() { cin>>m>>n; for(int i=1;i<=n;i++) { cin>>w[i]>>c[i]; } for(int i=1;i<=n;i++) { for(int v=1;v<=m;v++) { if(v<w[i]) { f[i][v]=f[i-1][v]; } else { if(f[i-1][v]>f[i][v-w[i]]+c[i]) { f[i][v]=f[i-1][v]; } else { f[i][v]=f[i][v-w[i]]+c[i]; } } } } cout<<"max="<<f[n][m]; return 0; }