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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys

def main():
	readline = sys.stdin.readline
	write = sys.stdout.write

	def gcd(m, n):
		while n:
			(m, n) = (n, m % n)
		return m

	def init(p, q=1):
		g = gcd(p, q)
		return (p // g, q // g)

	def add(A, B):
		(pa, qa) = A
		(pb, qb) = B
		if pa == 0:
			return B
		if pb == 0:
			return A
		g = gcd(qa, qb)
		ra = pa * qb // g + pb * qa // g
		rb = qa * qb // g
		g = gcd(ra, rb)
		return (ra // g, rb // g)
	INF = 10 ** 18

	def cp(X):
		(vw, pf, vf, th) = X
		if vw == 0:
			return INF
		return th / vw
	while 1:
		N = int(readline())
		if N == 0:
			break
		pw = int(readline())
		P = [list(map(int, readline().split())) for i in range(N)]
		P.append((1, 0, 1, 0))
		P.sort(key=cp)
		A = [init(0)] * (N + 1)
		B = [init(0)] * (N + 1)
		a = b = init(0)
		a = init(pw)
		for (i, (vw, pf, vf, th)) in enumerate(P):
			if vw == 0:
				if th > 0:
					b = add(b, (th * pf, vf))
				continue
			if vw > 0:
				if th ^ vw >= 0:
					a = add(a, (-vw * pf, vf))
					b = add(b, (th * pf, vf))
					A[i] = init(vw * pf, vf)
					B[i] = init(-th * pf, vf)
			elif th ^ vw >= 0:
				A[i] = init(-vw * pf, vf)
				B[i] = init(th * pf, vf)
			else:
				a = add(a, (-vw * pf, vf))
				b = add(b, (th * pf, vf))
		ans = INF
		for (i, (vw, pf, vf, th)) in enumerate(P):
			if vw == 0:
				continue
			if th ^ vw < 0:
				continue
			a = add(a, A[i])
			b = add(b, B[i])
			(pa, qa) = a
			(pb, qb) = b
			v = (pa * th * qb + pb * vw * qa) / (vw * qa * qb)
			if ans + 0.01 < v:
				break
			ans = min(ans, v)
		write('%.016f\n' % ans)
main()