#include<bits/stdc++.h> using namespace std; int m,n; int w[31],c[31]; int f[31][201]; 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<<f[n][m]; return 0; }