In this problem, you are asked to “maximize the minimum value of” \(W\).
In competitive programming, maximizing the minimum value, or vice versa, can be typically achieved by fixing a preliminary answer and check if that answer is possible to perform a binary search.
Indeed, this problem can be solved with the binary search approach. Consider the following decision problem:

if the budget is \(w\) yen, can we achieve a production capacity of at least \(w\)?

To solve this problem, it is sufficient to find the minimum amount of money to have \(W_i \ge w\) for all \(i\). From now on, we will consider the following problem:

how much money is required to process at least \(w\) products in process \(i\)?

Actually, we have the following fact:

for a way to buy machine with minimum amount of money to process at least \(w\) products in process \(i\), at least one of the following is true:

• \(S_i\) is introduced \(A_i\) products or less.
• \(T_i\) is introduced \(B_i\) products or less.

Proof:
The conjecture is equivalent to:

• In an optimal solution, at least one of machine \(S_i\) or \(T_i\) has a capacity to process \(A_iB_i\) products or less.

\(B_i\) instances of machine \(S_i\) and \(A_i\) instances of machine \(T_i\) are both capable of processing \(A_iB_i\) products. Since they are interchangeable, we may repeatedly substitute one set for another, whichever is cheaper, as many times as possible. Now we arrive at the conclusion above.

Based on this fact, one can brute-force the number of machine \(S_i\) up to \(B_i\), and the number of machine \(T_i\) up to \(A_i\), to solve it in \(O(A_i+B_i)\) time.

Let us go back to the original problem, which can be solved in the following outline:

• Do binary search over the answer \(w\) to this problem.
  • For each \(i=1,2,\dots,N\), find the minimum amount of money required to have \(W_i \ge w\).
  • If their sum does not exceed \(X\), the answer is \(w\) or greater; otherwise, the answer is less than \(w\).

By the constraints, one can prove that the answer is not more than \(10^9\), so it is sufficient to perform the binary search within this range.

The time complexity is \(O(N(A_i+B_i) \log(X (A_i+B_i)))\).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

long long div_ceil(long long a,long long b){
  return (a+b-1)/b;
}

long long solve(
  long long n,long long x,vector<long long> a,vector<long long> p,vector<long long> b,vector<long long> q
){
  long long l=1,r=1000000007;
  while(l<=r){
    long long te=(l+r)/2;
    long long rem=x;

    for(long long i=0;i<n;i++){
      long long sub=4e18;
      for(long long j=0;j<=b[i];j++){
        long long cur=j*p[i];
        long long rte=max(0ll,te-a[i]*j);
        cur+=div_ceil(rte,b[i])*q[i];

        sub=min(sub,cur);
      }
      for(long long j=0;j<=a[i];j++){
        long long cur=j*q[i];
        long long rte=max(0ll,te-b[i]*j);
        cur+=div_ceil(rte,a[i])*p[i];

        sub=min(sub,cur);
      }
      rem-=sub;
      if(rem<0){break;}
    }

    if(rem>=0){l=te+1;}
    else{r=te-1;}
  }
  return r;
}

int main(){
  long long n,x;
  cin >> n >> x;
  vector<long long> a(n),p(n),b(n),q(n);
  for(int i=0;i<n;i++){
    cin >> a[i] >> p[i] >> b[i] >> q[i];
  }

  cout << solve(n,x,a,p,b,q) << "\n";
  return 0;
}