Problem: Problem Statement

We have planted $N$ flower seeds, all of which come into different flowers. We want to make all the flowers come out together.

Each plant has a value called vitality, which is initially zero. Watering and spreading fertilizers cause changes on it, and the $i$-th plant will come into flower if its vitality is equal to or greater than $\mathit{th}_i$. Note that $\mathit{th}_i$ may be negative because some flowers require no additional nutrition.

Watering effects on all the plants. Watering the plants with $W$ liters of water changes the vitality of the $i$-th plant by $W \times \mathit{vw}_i$ for all $i$ ($1 \le i \le n$), and costs $W \times \mathit{pw}$ yen, where $W$ need not be an integer. $\mathit{vw}_i$ may be negative because some flowers hate water.

We have $N$ kinds of fertilizers, and the $i$-th fertilizer effects only on the $i$-th plant. Spreading $F_i$ kilograms of the $i$-th fertilizer changes the vitality of the $i$-th plant by $F_i \times \mathit{vf}_i$, and costs $F_i \times \mathit{pf}_i$ yen, where $F_i$ need not be an integer as well. Each fertilizer is specially made for the corresponding plant, therefore $\mathit{vf}_i$ is guaranteed to be positive.

Of course, we also want to minimize the cost. Formally, our purpose is described as "to minimize $W \times \mathit{pw} + \sum_{i=1}^{N}(F_i \times \mathit{pf}_i)$ under $W \times \mathit{vw}_i + F_i \times \mathit{vf}_i \ge \mathit{th}_i$, $W \ge 0$, and $F_i \ge 0$ for all $i$ ($1 \le i \le N$)". Your task is to calculate the minimum cost.

Input

The input consists of multiple datasets. The number of datasets does not exceed $100$, and the data size of the input does not exceed $20\mathrm{MB}$. Each dataset is formatted as follows.

> $N$
> $\mathit{pw}$
> $\mathit{vw}_1$ $\mathit{pf}_1$ $\mathit{vf}_1$ $\mathit{th}_1$
> :
> :
> $\mathit{vw}_N$ $\mathit{pf}_N$ $\mathit{vf}_N$ $\mathit{th}_N$

The first line of a dataset contains a single integer $N$, number of flower seeds. The second line of a dataset contains a single integer $\mathit{pw}$, cost of watering one liter. Each of the following $N$ lines describes a flower. The $i$-th line contains four integers, $\mathit{vw}_i$, $\mathit{pf}_i$, $\mathit{vf}_i$, and $\mathit{th}_i$, separated by a space.

You can assume that $1 \le N \le 10^5$, $1 \le \mathit{pw} \le 100$, $-100 \le \mathit{vw}_i \le 100$, $1 \le \mathit{pf}_i \le 100$, $1 \le \mathit{vf}_i \le 100$, and $-100 \le \mathit{th}_i \le 100$.

The end of the input is indicated by a line containing a zero.

Output

For each dataset, output a line containing the minimum cost to make all the flowers come out. The output must have an absolute or relative error at most $10^{-4}$.

Sample Input


3
10
4 3 4 10
5 4 5 20
6 5 6 30
3
7
-4 3 4 -10
5 4 5 20
6 5 6 30
3
1
-4 3 4 -10
-5 4 5 -20
6 5 6 30
3
10
-4 3 4 -10
-5 4 5 -20
-6 5 6 -30
0

Output for the Sample Input


43.5
36
13.5
0





Example

Input

3
10
4 3 4 10
5 4 5 20
6 5 6 30
3
7
-4 3 4 -10
5 4 5 20
6 5 6 30
3
1
-4 3 4 -10
-5 4 5 -20
6 5 6 30
3
10
-4 3 4 -10
-5 4 5 -20
-6 5 6 -30
0


Output

43.5
36
13.5
0

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

typedef long double Real;

pair<Real, pair<int, bool> > flowers[SIZE];
Real alpha[SIZE], beta[SIZE];

Real calcCost(Real pw, Real sumA, Real sumB, Real l, Real r) {
  l = max(l, (Real)0.0);
  sumA += pw;

  if (l > r) return 1e20;

  if (sumA < 0) {
    return r * sumA + sumB;
  } else {
    return l * sumA + sumB;
  }
}

bool solve() {
  int N;
  int pw, vw, pf, vf, th;

  scanf("%d", &N);

  if (N == 0) return false;

  scanf("%d", &pw);

  Real sumA = 0, sumB = 0;

  for (int i=0; i<N; i++) {
    scanf("%d%d%d%d", &vw, &pf, &vf, &th);

    Real limit = 1e20;

    //alpha * x + beta = cost
    alpha[i] = -(Real)vw * pf / vf;
    beta[i] = (Real)th * pf / vf;

    bool add = vw < 0; //alpha[i] > 0;

    if (!add) { // alpha[i] < 0
      sumA += alpha[i];
      sumB += beta[i];

      //消去位置
      if (th >= 0 && vw == 0) // beta[i] >= 0 && alpha[i] == 0
        limit = 1e20;
      if (th < 0 && vw == 0) // beta[i] < 0 && alpha[i] == 0
        limit = -1;

      if (th >= 0 && vw != 0) // beta[i] >= 0 && alpha[i] < 0
        limit = -beta[i] / alpha[i];
      if (th < 0 && vw != 0) // beta[i] < 0 && alpha[i] < 0
        limit = -1;

    } else {
      //追加位置

      if (th < 0) // beta[i] < 0 && alpha[i] > 0
        limit = -beta[i] / alpha[i];
      else // beta[i] > 0 && alpha[i] > 0
        limit = -1;
    }

    flowers[i] = {limit, {i, add}};
  }

  sort(flowers, flowers+N);

  Real ans = 1e30;
  Real prev = 0;

  for (int i=0; i<N; i++) {
    Real limit = flowers[i].first;
    int idx = flowers[i].second.first;
    bool add = flowers[i].second.second;

    if (prev > 1e15) break;

    ans = min(ans, calcCost(pw, sumA, sumB, prev, limit));

    //debug(sumA); debug(sumB); debug(prev); debug(calcCost(pw, sumA, sumB, prev, limit));

    if (add) {
      sumA += alpha[idx];
      sumB += beta[idx];
    } else {
      sumA -= alpha[idx];
      sumB -= beta[idx];
    }

    prev = limit;
  }

  printf("%.10lf\n", (double)ans + 1e-11);

  return true;
}

int main(){

  while(solve());

  return 0;
}