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<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct flower
{
    int w;
    int f_cost;
    int f;
    int th;
    double w_th;
    void read()
    {
        scanf("%d%d%d%d",&w,&f_cost,&f,&th);
        w_th=(double)th/w;
    }
    friend bool operator < (const flower &a,const flower &b)
    {
        return a.w_th<b.w_th;
    }
};
flower a[100005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    for (;;)
    {
        int n,m;
        scanf("%d",&n);
        if (n==0) return 0;
        scanf("%d",&m);
        int i;
        double ans=0;
        for (i=0;i<n;i++)
        {
            a[i].read();
            if ((a[i].w>=0)&&(a[i].th<=0))
            {
                i--;
                n--;
            }
            else if (a[i].w==0)
            {
                ans+=a[i].th*a[i].f_cost/(double)a[i].f;
                i--;
                n--;
            }
        }
        sort(a,a+n);
        double k=0;
        double last_ans=0;
        double last_sol=0;
        for (i=0;i<n;i++)
        {
            if (a[i].th>0)
            {
                last_ans+=a[i].th*a[i].f_cost/(double)a[i].f;
                k-=a[i].w*a[i].f_cost/(double)a[i].f;
            }
        }
        double min_ans=last_ans;
        for (i=0;i<n;i++)
        {
            if (a[i].w_th<0) continue;
            double delta=a[i].w_th-last_sol;
            last_sol=a[i].w_th;
            last_ans+=delta*k;
            last_ans+=delta*m;
            min_ans=min(min_ans,last_ans);
            if (a[i].th>0)
            {
                k+=a[i].w*a[i].f_cost/(double)a[i].f;
            }
            else
            {
                k-=a[i].w*a[i].f_cost/(double)a[i].f;
            }
        }
        printf("%.5lf\n",ans+min_ans);
    }
    return 0;
}