rt

#include<ctime>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=105;
int n,m,ans;
pair<int,int>a[MAXN];
inline void dfs(int now,int sum,int res){
    if(double(clock())/CLOCKS_PER_SEC>0.0025){
        cout<<ans<<endl;
        exit(0);
    }
    if(now>n){ans=max(ans,sum);return;}
    if(res*a[now].second+sum*a[now].first<=ans*a[now].first)return;
    if(a[now].first<=res)dfs(now+1,sum+a[now].second,res-a[now].first);
    dfs(now+1,sum,res);
}
inline bool cmp(pair<int,int>a,pair<int,int>b){
    return a.second*b.first>b.second*a.first;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(register int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
    sort(a+1,a+n+1,cmp);
    dfs(1,0,m);
    cout<<ans;
}

https://www.luogu.com.cn/record/228677733 https://www.luogu.com.cn/record/228689746 https://www.luogu.com.cn/record/228677733