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

#include <iostream>
typedef long long ll;
using namespace std;
const ll MAXN = 105, MAXANS = static_cast<ll>(1e10) + 7;
ll n, x, mach[MAXN][6];

inline bool check(ll needCap) {
    ll sumYen = 0;
    for (int i = 1; i <= n; i++) {
        if (sumYen > x)
            return false;

        ll cap1 = mach[i][1], p1 = mach[i][2], cap2 = mach[i][3], p2 = mach[i][4];
        ll minYen;

        // Need these many machines of type 1 and type 2 to meet the capacity
        ll needMach1 = (needCap - 1) / cap1 + 1;
        ll needMach2 = (needCap - 1) / cap2 + 1;

        // Option 1: Using only machines of type 1 or type 2
        minYen = min(needMach1 * p1, needMach2 * p2);

        // Option 2: Combination of both types
        ll firstMach1 = needCap / cap1;
        ll remainMach2 = (needCap - firstMach1 * cap1 - 1) / cap2 + 1;
        if (remainMach2 >= 0) {
            ll priceComb1 = firstMach1 * p1 + remainMach2 * p2;
            minYen = min(minYen, priceComb1);
        }

        ll firstMach2 = needCap / cap2;
        ll remainMach1 = (needCap - firstMach2 * cap2 - 1) / cap1 + 1;
        if (remainMach1 >= 0) {
            ll priceComb2 = firstMach2 * p2 + remainMach1 * p1;
            minYen = min(minYen, priceComb2);
        }

        // Add to total cost
        sumYen += minYen;
    }

    return sumYen <= x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        // cap1, price1, cap2, price2
        cin >> mach[i][1] >> mach[i][2] >> mach[i][3] >> mach[i][4];
    }

    ll l = 0, r = MAXANS;
    while (l < r) {
        ll mid = (l + r + 1) >> 1;
        if (check(mid)) 
            l = mid;
        else 
            r = mid - 1;
    }

    cout << l << endl;
    return 0;
}