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 <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

double pw;
vector<double> vw, pf, vf, th;
double calc(double W) {
    int N = vw.size();
    double res = W * pw;

    REP(i, N) {
        double F = (th[i] - vw[i] * W) / vf[i];
        if(F > 0) {
            res += pf[i] * F;
        }
    }

    return res;
}

double find_min(double a, double b, double f(double)) {
    REP(_, 86) {
        double c = (a * 2 + b) / 3;
        double d = (a + b * 2) / 3;
        if(f(c) < f(d)) {
            b = d;
        } else {
            a = c;
        }
    }
    return (a + b) / 2;
}
static const double RATIO = (1 + sqrt(5.0)) * 0.5;
double find_min_fast(double left, double right, double f(double)){
	double leftValue = f((left * RATIO + right) / (1 + RATIO));
	double rightValue = f((left + right * RATIO) / (1 + RATIO));
	for (int loop = 0; loop < 72; ++loop){
		if (leftValue < rightValue){
			right = (left + right * RATIO) / (1 + RATIO);
			rightValue = leftValue;
			leftValue = f((left * RATIO + right) / (1 + RATIO));
		} else {
			left = (left * RATIO + right) / (1 + RATIO);
			leftValue = rightValue;
			rightValue = f((left + right * RATIO) / (1 + RATIO));
		}
	}
	if (leftValue < rightValue){
		right = (left + right * RATIO) / (1 + RATIO);
	} else {
		left = (left * RATIO + right) / (1 + RATIO);
	}
	return (right + left) * 0.5;
}

int main(){
    int N;
    while(cin >> N && N > 0) {
        cin >> pw;
        vw.resize(N);
        pf.resize(N);
        vf.resize(N);
        th.resize(N);
        REP(i, N) {
            cin >> vw[i] >> pf[i] >> vf[i] >> th[i];
        }

        /*
        double lb = 0, ub = 1000;
        REP(_, 100) {
            double left = (lb * 2 + ub) / 3;
            double right = (lb + ub * 2) / 3;
            if(calc(left) < calc(right)) {
                ub = right;
            } else {
                lb = left;
            }
        }
        */

        double x = find_min_fast(0, 1000, calc);

        printf("%.12lf\n", calc(x));
    }
    return 0;
}