#include<iostream> using namespace std; int a,b,c,d[10025],e[10025],f,g[10025]; int main() { cin>>a>>b; for(c=1;c<=a;c++) cin>>d[c]>>e[c]; for(c=1;c<=a;c++) for(f=d[c];f<=a;f++) if(g[f-d[c]]+e[c]>g[f]) g[f]=g[f-d[c]]+e[c]; cout<<g[a]; return 0; }