この問題は、 \(W\) の「最小値を最大化」する問題です。
競技プログラミングにおいて、「最小値を最大化」(または「最大値を最小化」) する問題は、答えとなる値を仮に決め打って、その値が達成可能かを判定しながら二分探索する (いわゆる 決め打ち二分探索 ) テクニックがしばしば有効です。
現に、今回は決め打ち二分探索を用いてこの問題を解くことができます。 以下の判定問題を解くことを考えましょう。

予算を \(X\) 円までかけることができるとき、製造能力を \(w\) 以上にできるか?

この問題を解くためには、全ての \(i\) について \(W_i \ge w\) とするための最小の金額を求めれば良いことになります。以降、次の問題を考えます。

工程 \(i\) で製品を \(w\) 個以上処理できるようにするためにかかる最小の費用はいくらか?

実は、以下の事柄が成り立ちます。

工程 \(i\) を \(w\) 個以上処理できる機械の導入方法のうち最小の金額を達成するものでは、次の少なくとも一方が満たされる。

• 機械 \(S_i\) が \(B_i\) 台以下しか導入されない。
• 機械 \(T_i\) が \(A_i\) 台以下しか導入されない。

証明:
上記を言い換えると、次のようになります。

• 最適解において、機械 \(S_i, T_i\) のどちらかについて、 \(A_iB_i\) 個分以下の処理能力しか持たせなくて良い。

\(B_i\) 台の機械 \(S_i\) と \(A_i\) 台の機械 \(T_i\) はどちらも \(A_iB_i\) 個分の処理能力であり、この \(2\) つは相互に交換可能である。ならば、この \(2\) つのうちコストの安いものに交換できる限り交換すればよい。このことを言い換えると上記の事柄となる。

この事柄を使うことで、「機械 \(S_i\) の個数を \(B_i\) 以下で全探索」「機械 \(T_i\) の個数を \(A_i\) 以下で全探索」するとこの問題を時間計算量 \(O(A_i+B_i)\) で解くことができます。

元の問題に戻ります。 元の問題は以下の構造で解くことができます。

• この問題の答え \(w\) を二分探索する。
  • 全ての \(i=1,2,\dots,N\) について、 \(W_i \ge w\) とするための最小金額を足し合わせる。
  • その金額が \(X\) 以下なら答えは \(w\) 以上であり、そうでないとき答えは \(w\) 未満である。

制約から、答えは \(10^9\) 以下であることが証明できるので、この範囲で二分探索すればよいです。

時間計算量は \(O(N(A_i+B_i) \log(X (A_i+B_i)))\) です。

実装例 (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;
}