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:
//Name: Flowers
//Level: 3
//Category: 貪欲,Greedy,Priority queue
//Note:

/**
 * 水をWリットル与えてから、それぞれの花ごとに肥料で調整していくので、Wを決定すれば全体のコストも求められる。
 * WをΔWだけ増やすと、それぞれの花で後で必要な肥料の量がvwΔW / vfだけ減少するから、肥料のコストはpf × vwΔW / vfだけ減少する
 * （vwが負の場合、コストは増加することになる）。
 * また、水そのものの費用がpwΔWだけかかる。
 *
 * 水を増やしていくと発生するイベントは
 * ・ある花のvitalityがthを超え、肥料のコストが影響しなくなる。
 * ・ある花のvitalityがthを割り、それまで必要のなかった肥料を増やす必要が出てくる。
 * これらのいずれも、水やりのコストを上げる方向に作用する。
 * したがって、ΔWの係数 pw - Σpf_i × vw_i / vf_i は水やりを進めるにしたがって単調増加していく。
 * この係数が負になっている間は、水やりを続けると得をするが、正になると肥料のみに切り替えたほうがよくなる。
 *
 * このようなイベントが発生する時刻は固定なので、あらかじめ求めてからソートしておき、係数の変化をシミュレーションすればよい。
 * オーダーは O(N log N)。
 */

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool solve() {
    int N;
    if(!(cin >> N)) return false;
    if(!N) return false;
    
    double PW;
    cin >> PW;
    vector<pair<double,double>> ds;
    double ans = 0;
    double cur_eff = PW;
    for(int i = 0; i < N; ++i) {
        double vw, pf, vf, th;
        cin >> vw >> pf >> vf >> th;
        if(th >= 0) ans += th / vf * pf;
        const double t = th / vw;
        const double eff = pf * vw / vf;
        if(th >= 0 && vw > 0) {
            ds.emplace_back(t, eff);
            cur_eff -= eff;
        } else if(th <= 0 && vw < 0) {
            ds.emplace_back(t, -eff);
        } else if(th >= 0 && vw < 0) {
            cur_eff -= eff;
        }
    }
    sort(begin(ds), end(ds));
    double prev = 0;
    for(auto &d : ds) {
        if(cur_eff > 0) break;
        //cout << cur_eff << ": " << ans << endl;
        ans += cur_eff * (d.first - prev);
        cur_eff += d.second;
        prev = d.first;
    }
    cout << ans << endl;
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);

    while(solve()) ;
    return 0;
}