https://atcoder.jp/contests/abc374/submissions/58488655

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=150;
int n,m,maxn=0x3f3f3f3f3f3f,ans,amns;
int a[N],p[N],b[N],q[N];
int minn[N][N];
int dp[N][N];
signed main(){
    scanf("%lld%lld",&n,&m);
    memset(dp,0x3f,sizeof(dp));
    memset(minn,0x3f,sizeof(minn));
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld%lld",&a[i],&p[i],&b[i],&q[i]);
        maxn=min(maxn,max(m/p[i]*a[i]+a[i],m/q[i]*b[i]+b[i]));
    }
    int l=0,r=maxn;
    while(l<=r){
        int i=(l+r)>>1;
        // cout<<i<<endl;
        int num=0;bool flag=1;
        for(int j=1;j<=n;j++){
            int minc=0x3f3f3f3f3f3f3f;
            if(a[j]*q[j]-b[j]*p[j]>0){
                for(int k=0;k<=min(100ll,(i+a[j]-1)/a[j]);k++){
                    minc=min(minc,(int)(q[j]*k+p[j]*max(((i-b[j]*k+a[j]-1)/a[j]),0ll)));
                }
            }
            else if(a[j]*q[j]-b[j]*p[j]==0){
                for(int k=0;k<=min(100ll,(i+b[j]-1)/b[j]);k++){
                    minc=min(minc,(int)(p[j]*k+q[j]*max(((i-a[j]*k+b[j]-1)/b[j]),0ll)));
                }
                for(int k=0;k<=min(100ll,(i+a[j]-1)/a[j]);k++){
                    minc=min(minc,(int)(q[j]*k+p[j]*max(((i-b[j]*k+a[j]-1)/a[j]),0ll)));
                }
            }
            else{
                for(int k=0;k<=min(100ll,(i+b[j]-1)/b[j]);k++){
                    minc=min(minc,(int)(p[j]*k+q[j]*max(((i-a[j]*k+b[j]-1)/b[j]),0ll)));
                }
            }
            num+=minc;
            // cout<<"minc:"<<minc<<endl;
            // cout<<" "<<num<<endl;
            if(num>m){
                flag=0;
            }
        }
        if(flag){
            l=i+1;
            ans=max(ans,i);
        }
        else r=i-1;

    }
    cout<<ans<<endl;
    return 0;
}