#include<bits/stdc++.h> using namespace std; const int M=10010,N=10010; int dp[M]; int main(){ memset(dp,0x3f,sizeof dp); int m,n; cin>>m>>n; for(int i=1;i<=n;i++){ int si,ti; cin>>si>>ti; for(int j=ti;j<=m;j++){ dp[j]=min(dp[j],dp[j-ti]+si); } } cout<<dp[m]<<endl; return 0; }