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 "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	while (cin >> N, N) {
		long double wcost;
		cin >> wcost;
		vector<long double>wgain(N);
		vector<long double>cost(N);
		vector<long double>gain(N);
		vector<long double>goal(N);
		vector<long double>v;
		v.push_back(0);
		long double plusadd = 0;
		long double minusadd = 0;
		long double box = 0;
		priority_queue<pair<long double, long double>,vector<pair<long double, long double>>,greater<pair<long double, long double>>>plusPQ;
		priority_queue<pair<long double, long double>,vector<pair<long double, long double>>,greater<pair<long double, long double>>>minusPQ;
		for (int i = 0; i < N; i++) {
			cin >> wgain[i] >> cost[i] >> gain[i] >> goal[i];
			if (goal[i] > 0) {
				box += goal[i] / gain[i] * cost[i];
			}
			if (wgain[i] > 0 && goal[i] / wgain[i] > 0) {
				v.push_back(goal[i] / wgain[i]);
				plusPQ.push({ goal[i] / wgain[i],wgain[i] / gain[i] * cost[i] });
				plusadd -= wgain[i] / gain[i] * cost[i];
			}
			else if (wgain[i] < 0) {
				if (goal[i] / wgain[i] > 0) {
					v.push_back(goal[i] / wgain[i]);
					minusPQ.push({ goal[i] / wgain[i],-wgain[i] / gain[i] * cost[i] });
				}
				else {
					minusadd -= wgain[i] / gain[i] * cost[i];
				}
			}
		}
		long double ans = box;
		sort(v.begin(), v.end());
		long double bef = 0;
		for (auto i : v) {
			box += plusadd * (i - bef);
			box += minusadd * (i - bef);
			while (!plusPQ.empty() && abs(plusPQ.top().first - i) < EPS) {
				plusadd += plusPQ.top().second;
				plusPQ.pop();
			}
			while (!minusPQ.empty() && abs(minusPQ.top().first - i) < EPS) {
				minusadd += minusPQ.top().second;
				minusPQ.pop();
			}
			box += (i - bef)*wcost;
			ans = min(ans, box);
			bef = i;
		}
		cout << setprecision(20) << ans << endl;
	}
}