You have $N$ items that you want to put them into a knapsack of capacity $W$. Item $i$ ($1 \le i \le N$) has weight $w_i$ and value $v_i$ for the weight.

When you put some items into the knapsack, the following conditions must be satisfied:

* The total value of the items is as large as possible.
* The total weight of the selected items is at most $W$.
* You can break some items if you want. If you put $w'$($0 \le w' \le w_i$) of item $i$, its value becomes $\displaystyle v_i \times \frac{w'}{w_i}.$



Find the maximum total value of items in the knapsack.

Constraints

* $1 \le N \le 10^5$
* $1 \le W \le 10^9$
* $1 \le v_i \le 10^9 (1 \le i \le N)$
* $1 \le w_i \le 10^9 (1 \le i \le N)$

Input


$N$ $W$
$v_1$ $w_1$
$v_2$ $w_2$
:
$v_N$ $w_N$


The first line consists of the integers $N$ and $W$. In the following $N$ lines, the value and weight of the $i$-th item are given.

Output

Print the maximum total value of the items in a line. The output must not contain an error greater than $10^{-6}$.

Examples

Input

3 50
60 10
100 20
120 30


Output

240


Input

3 50
60 13
100 23
120 33


Output

210.90909091


Input

1 100
100000 100000


Output

100

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(N, W) = map(int, input().split())
W_calc = W
ans = 0
items = []
for _ in range(N):
	(v, w) = map(int, input().split())
	density = v / w
	items.append([density, v, w])
items.sort(reverse=True)
for (density, v, w) in items:
	if w < W_calc:
		W_calc -= w
		ans += v
	else:
		ans += W_calc * density
		break
print(ans)


(N, W) = map(int, input().split())
items = []
for _ in range(N):
	(v, w) = map(int, input().split())
	items.append((v / w, v, w))
items.sort()
ans = 0
while W > 0 and items:
	(r, v, w) = items.pop()
	if W >= w:
		W -= w
		ans += v
	else:
		ans += v * W / w
		W = 0
print(ans)


import sys
(n, W) = map(int, sys.stdin.readline().split())
val = []
for i in range(n):
	val.append(list(map(int, sys.stdin.readline().split())))
total = 0
for vv in sorted(val, key=lambda x: x[0] / x[1], reverse=True):
	if W >= vv[1]:
		W -= vv[1]
		total += vv[0]
	else:
		total += W * vv[0] / vv[1]
		break
print(total)


(n, w) = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort(key=lambda x: x[0] / x[1], reverse=True)
rest = w
ans = 0
for (val, wei) in lst:
	if rest >= wei:
		ans += val
		rest -= wei
	else:
		ans += val / wei * rest
		break
print(ans)


readline = open(0).readline
(N, W) = map(int, readline().split())
R = []
for i in range(N):
	(v, w) = map(int, readline().split())
	R.append((v / w, v, w))
R.sort(reverse=1)
ans = 0
for (_, v, w) in R:
	c = min(w, W)
	W -= c
	ans += c * v / w
open(1, 'w').write('%.010f\n' % ans)


(n, wmax) = map(int, input().split())
U = []
for _ in range(n):
	(v, w) = map(int, input().split())
	u = v / w
	U.append([-u, v, w])
U.sort()
remains = wmax
i = 0
ans = 0
while True:
	try:
		if remains > U[i][2]:
			remains -= U[i][2]
			ans += U[i][1]
			i += 1
		else:
			ans += U[i][1] * remains / U[i][2]
			break
	except:
		break
print(ans)


import sys, collections
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 10

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	(N, W) = LI()
	vw = [LI() for _ in range(N)]
	vw.sort(key=lambda x: x[0] / x[1], reverse=True)
	ans = 0
	i = 0
	while i < N and W - vw[i][1] > 0:
		ans += vw[i][0]
		W -= vw[i][1]
		i += 1
	if i < N:
		ans += vw[i][0] * W / vw[i][1]
	print(ans)
resolve()


(n, w) = map(int, input().split())
val_w = []
for i in range(n):
	(a, b) = map(int, input().split())
	val_w += [(-a / b, b)]
val_w.sort()
Sum = 0
i = 0
while w and i <= n - 1:
	wei = min(w, val_w[i][1])
	Sum += -val_w[i][0] * wei
	w -= wei
	i += 1
print(Sum)


class Item:

	def __init__(self, v, w):
		self.v = v
		self.w = w
		self.r = v / w
(n, w) = map(int, input().split())
items = []
for i in range(n):
	(vi, wi) = map(int, input().split())
	items.append(Item(vi, wi))
items.sort(key=lambda x: x.r, reverse=True)
total = 0
remain = w
for i in range(n):
	vi = items[i].v
	wi = items[i].w
	ri = items[i].r
	if wi <= remain:
		total += vi
		remain -= wi
	else:
		total += ri * remain
		break
print(total)


import sys
input = sys.stdin.readline
p = []
(n, w) = map(int, input().split())
for i in range(n):
	(a, b) = map(int, input().split())
	p.append([a / b, a, b])
p.sort(key=lambda x: -x[0])
ans = 0
i = 0
while w > 0 and i < n:
	if w >= p[i][2]:
		ans += p[i][1]
	else:
		ans += p[i][1] * (w / p[i][2])
		break
	w -= p[i][2]
	i += 1
print(ans)


import heapq
(n, w) = [int(i) for i in input().split()]
res = 0
pq = []
for _ in range(n):
	(_v, _w) = [int(i) for i in input().split()]
	e = _v / _w
	heapq.heappush(pq, (-e, _v, _w))
while w > 0 and pq:
	(e, value, weight) = heapq.heappop(pq)
	if w >= weight:
		res += value
		w -= weight
	else:
		res += -e * w
		w = 0
print(res)


from collections import namedtuple
I = namedtuple('I', 'k v w')
(n, w) = map(int, input().split())
s = []
for i in range(n):
	(vi, wi) = map(int, input().split())
	s.append(I(vi / wi, vi, wi))
s.sort()
ans = 0
while w > 0 and s != []:
	item = s.pop()
	if w < item.w:
		(a, b) = (item.v * w, item.w)
		if a % b == 0:
			ans += a // b
		else:
			ans += a / b
	else:
		ans += item.v
	w -= item.w
print(ans)


(N, W) = map(int, input().split())
R = []
for i in range(N):
	(v, w) = map(int, input().split())
	R.append((v / w, v, w))
R.sort(reverse=1)
ans = 0
for (_, v, w) in R:
	c = min(w, W)
	W -= c
	ans += c * v / w
print(ans)


first = list(map(int, input().split()))
(n, w) = (first[0], first[1])
data = []
for i in range(n):
	a = list(map(int, input().split()))
	vpwi = a[0] / a[1]
	data.append([vpwi, a[0], a[1]])
data.sort(reverse=True)
wtot = 0
vtot = 0
i = 0
for i in range(n):
	if wtot + data[i][2] <= w:
		wtot += data[i][2]
		vtot += data[i][1]
	else:
		vtot += data[i][0] * (w - wtot)
		break
print(vtot)


import heapq

def Main():
	(N, capacity) = map(int, input().split())
	w_list = list()
	for _ in range(N):
		(v, w) = map(int, input().split())
		heapq.heappush(w_list, [-1 * float(v / w), v, w])
	total_value = 0
	while len(w_list) != 0:
		item = heapq.heappop(w_list)
		value_per_weight = -1 * item[0]
		value = item[1]
		weight = item[2]
		if capacity >= weight:
			capacity -= weight
			total_value += value
		else:
			total_value += capacity * value_per_weight
			break
	print(total_value)
Main()


class Item:

	def __init__(self, v, w):
		self.v = v
		self.w = w
		self.r = v / w

	def __str__(self):
		s = 'v=' + str(self.v)
		s += ',w=' + str(self.w)
		s += ',r=' + str(self.r)
		return s
(n, w) = map(int, input().split())
items = []
for i in range(n):
	(vi, wi) = map(int, input().split())
	items.append(Item(vi, wi))
items.sort(key=lambda x: x.r, reverse=True)
total = 0
remain = w
for i in range(n):
	v = items[i].v
	w = items[i].w
	r = items[i].r
	if w <= remain:
		total += v
		remain -= w
	else:
		total += r * remain
		break
print(total)


(n, w) = map(int, input().split(' '))
pack = []
for _ in range(n):
	(x, y) = map(int, input().split(' '))
	pack.append([x / y, x, y])
pack.sort()
pp = pack[::-1]
sum = 0
for ele in pp:
	if w - ele[2] > 0:
		sum += ele[1]
		w = w - ele[2]
	else:
		sum += ele[0] * w
		break
print(sum)


readline = open(0).readline
(N, W) = map(int, readline().split())
R = []
for i in range(N):
	(v, w) = map(int, readline().split())
	R.append((v / w, v, w))
R.sort(reverse=1)
ans = 0
for (_, v, w) in R:
	c = min(w, W)
	W -= c
	ans += c * v / w
open(1, 'w').write('%.010f\n' % ans)


(N, W) = map(int, input().split())
V = [None] * N
ans = 0
for i in range(N):
	(v, w) = map(int, input().split())
	V[i] = [v / w, w]
V.sort(reverse=True)
for (v, w) in V:
	if W > w:
		W -= w
		ans += v * w
	else:
		ans += v * W
		break
print(ans)


(N, W) = [int(i) for i in input().split()]
VW = [[int(i) for i in input().split()] for _ in range(N)]
sVW = sorted(VW, key=lambda x: x[0] / x[1], reverse=True)
ans = 0
for i in sVW:
	if W < i[1]:
		ans += i[0] * W / i[1]
		break
	else:
		ans += i[0]
		W -= i[1]
print(ans)


def main():
	(N, W) = map(int, input().split())
	vw = [list(map(int, input().split())) for _ in range(N)]
	for i in range(N):
		vw[i].append(vw[i][0] / vw[i][1])
	vw.sort(reverse=True, key=lambda x: x[2])
	(val, wei) = (0, 0)
	for i in range(N):
		if wei + vw[i][1] <= W:
			val += vw[i][0]
			wei += vw[i][1]
		elif wei < W:
			val += vw[i][0] * (W - wei) / vw[i][1]
			wei = W
		else:
			break
	print(val)
main()


import os
import sys

def main():
	(N, W) = map(int, input().split())
	p = []
	for _ in range(N):
		(v, w) = map(int, input().split())
		p.append([v / w, v, w])
	p.sort(reverse=True)
	index = 0
	profit = 0
	while W > 0 and index < N:
		if W >= p[index][2]:
			profit += p[index][1]
			W -= p[index][2]
		else:
			profit += p[index][1] * W / p[index][2]
			W -= W
		index += 1
	print(profit)
main()


(N, W) = map(lambda x: int(x), input().split())
items = [[0, 0] for _ in range(N)]
for i in range(N):
	items[i] = list(map(lambda x: int(x), input().split()))
items = sorted(items, key=lambda x: -x[0] / x[1])
total_value = 0.0
total_weight = 0.0
for (v, w) in items:
	if total_weight + w <= W:
		total_weight += w
		total_value += v
		if W == total_weight:
			break
	else:
		rest_weight = W - total_weight
		total_value += v / w * rest_weight
		break
print(f'{total_value:.6f}')