It's a very unfortunate day for Volodya today. He got bad mark in algebra and was therefore forced to do some work in the kitchen, namely to cook borscht (traditional Russian soup). This should also improve his algebra skills.

According to the borscht recipe it consists of n ingredients that have to be mixed in proportion <image> litres (thus, there should be a1 ·x, ..., an ·x litres of corresponding ingredients mixed for some non-negative x). In the kitchen Volodya found out that he has b1, ..., bn litres of these ingredients at his disposal correspondingly. In order to correct his algebra mistakes he ought to cook as much soup as possible in a V litres volume pan (which means the amount of soup cooked can be between 0 and V litres). What is the volume of borscht Volodya will cook ultimately?

Input

The first line of the input contains two space-separated integers n and V (1 ≤ n ≤ 20, 1 ≤ V ≤ 10000). The next line contains n space-separated integers ai (1 ≤ ai ≤ 100). Finally, the last line contains n space-separated integers bi (0 ≤ bi ≤ 100).

Output

Your program should output just one real number — the volume of soup that Volodya will cook. Your answer must have a relative or absolute error less than 10 - 4.

Examples

Input

1 100
1
40


Output

40.0


Input

2 100
1 1
25 30


Output

50.0


Input

2 100
1 1
60 60


Output

100.0

Difficulty: MEDIUM
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, v) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
mini = 10 ** 9
for i in range(n):
	mini = min(mini, b[i] / a[i])
sm = 0
for i in range(n):
	sm = sm + mini * a[i]
print(min(sm, v))


(n, v) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
r = min((bi / ai for (ai, bi) in zip(a, b)))
print(min(v, r * sum(a)))


(n, V) = map(int, input().split())
(a, b) = (list(map(int, input().split())), list(map(int, input().split())))
x = b[0] / a[0]
for i in range(1, n):
	x = min(x, b[i] / a[i])
ans = 0
for i in a:
	ans += i * x
print(min(ans, V))


s = input().split()
s1 = input().split()
s2 = input().split()
n = int(s[0])
V = int(s[1])
a = []
b = []
num = 0
while num < n:
	a.append(int(s1[num]))
	num += 1
num = 0
while num < n:
	b.append(int(s2[num]))
	num += 1
x = float(b[0] / a[0])
ans = float(0)
num = 1
while num < n:
	x = min(x, b[num] / a[num])
	num += 1
num = 0
while num < n:
	ans = ans + a[num] * x
	num += 1
print('%.4f' % min(ans, V))


(n, V) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
Sa = sum(a)
m = min(b)
res = 0
for i in range(n):
	cur_r = 0
	for j in range(n):
		if b[j] >= a[j] * b[i] / a[i]:
			cur_r += a[j] * b[i] / a[i]
		else:
			break
	else:
		res = max(cur_r, res)
print(min(res, float(V)))


(n, v) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
w = [int(x) for x in range(n)]
for i in range(n):
	w[i] = float(b[i] / a[i])
w.sort()
print(min(w[0] * sum(a), v))


(n, V) = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
b = list(map(int, input().strip().split(' ')))
l = []
for i in range(n):
	l.append(b[i] / a[i])
m = min(l)
s = sum(a)
print(min(m * s, V))


(n, v) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
x = 100000
for i in range(n):
	b[i] /= a[i]
	x = min(b[i], x)
print(min(v, sum(a) * x))


(n, V) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = min((b[i] / a[i] for i in range(n)))
print(min(V, d * sum(a)))


(n, v) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = 10 ** 10
for i in range(n):
	x = min(x, b[i] / a[i])
ans = 0
for i in range(n):
	ans += x * a[i]
print(min(ans, v))


(n, vol) = map(int, input().split())
ratio = list(map(int, input().split()))
ing = list(map(int, input().split()))
ks = [ing[i] / ratio[i] for i in range(n)]
k = min(ks)
print(min(k * sum(ratio), vol))


from fractions import gcd

def Simplify(A):
	n = len(A)
	x = A[0]
	for i in range(1, n):
		x = gcd(x, A[i])
	for i in range(n):
		A[i] //= x
	return A
(n, V) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A = Simplify(A)
Voll = []
for i in range(n):
	Voll.append(B[i] / A[i])
M = min(Voll)
Vol = 0
for i in range(n):
	Vol += M * A[i]
print(min(V * 1.0, Vol))


(n, v) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
for i in range(n):
	c.append(b[i] / a[i])
k = min(c)
up = sum(a) * k
if up < v:
	print(up)
else:
	print(v)


(n, v) = map(int, input().split())
ar = list(map(int, input().split()))
br = list(map(int, input().split()))
x = min([br[i] / ar[i] for i in range(n)])
sm = min(v, sum(ar) * x)
print(sm)


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime
(n, v) = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
mini = 10 ** 9
for i in range(n):
	mini = min(mini, b[i] / a[i])
sm = 0
for i in range(n):
	sm += mini * a[i]
print(min(sm, v))


(n, v) = map(int, input().split())
a = [*map(float, input().split())]
b = [*map(float, input().split())]
item = 1e+24
for (x, y) in zip(a, b):
	item = min(item, y / x)
res = 0
summa = sum(a)
elem = v / summa
print(min(item, elem) * summa)


(n, v) = [int(x) for x in input().split()]
a = list(map(int, input().split()))
b = list(map(int, input().split()))
rate = v
for i in range(n):
	s = float(b[i] / a[i])
	rate = min(rate, s)
su = sum(a)
num = min(su * rate, v)
print('%.5f' % num)


def borsch(n, v, a, b):
	big = 10 ** 6
	ingridients = 0
	for i in range(n):
		big = min(big, b[i] / a[i])
	for i in range(n):
		ingridients += big * a[i]
	return min(ingridients, float(v))
(N, V) = [int(i) for i in input().split()]
lst1 = [int(x) for x in input().split()]
lst2 = [int(y) for y in input().split()]
print(borsch(N, V, lst1, lst2))


(n, v) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 0.0
r = 100000000.0
ans = 0.0
for it in range(100):
	m = l + (r - l) / 2
	f = 1
	sum = 0.0
	for i in range(n):
		sum += a[i] * m
		if a[i] * m > b[i]:
			f = 0
			break
	if sum > v:
		f = 0
	if f:
		ans = m
		l = m
	else:
		r = m
fans = 0.0
for i in range(n):
	fans += ans * a[i]
print(fans)


(n, v) = map(int, input().split())
ratio = list(map(int, input().split()))
lis = list(map(int, input().split()))
ans = []
for i in range(n):
	a = lis[i] / ratio[i]
	ans.append(a)
x = min(ans)
ss = 0
for i in ratio:
	ss += i * x
print(min(v, ss))


(n, capacity) = map(int, input().split())
proportions = list(map(int, input().split()))
ingredients = list(map(int, input().split()))
best_volume = 0
for (i, ingredientA) in enumerate(ingredients):
	proportionA = proportions[i]
	volume = 0
	feasible = True
	for (j, ingredientB) in enumerate(ingredients):
		proportionB = proportions[j]
		amount = ingredientA / proportionA * proportionB
		if amount > ingredientB + 1e-09:
			feasible = False
			break
		volume += amount
	if not feasible:
		continue
	volume = min(capacity, volume)
	best_volume = max(best_volume, volume)
print(best_volume)


(n, V) = list(map(int, input().split(' ')))
ratios = list(map(int, input().split(' ')))
available = list(map(int, input().split(' ')))
resulting = min([available[i] / ratios[i] for i in range(n)])
volume = sum([resulting * ratio for ratio in ratios])
print(min(volume, V))


(n, v) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
r = min((b[i] / a[i] * sum(a) for i in range(n)))
print(min(r, v))


s = input().split()
n = int(s[0])
v = int(s[1])
s = input().split()
a = [0] * n
sa = 0
for i in range(n):
	a[i] = int(s[i])
	sa += a[i]
s = input().split()
b = [0] * n
ok = 1
for i in range(n):
	b[i] = int(s[i])
	if b[i] == 0:
		ok = 0
x = [0] * n
if ok == 0:
	print(0)
else:
	for i in range(n):
		x[i] = a[i] * v / sa
	kmin = b[0] / x[0]
	for i in range(1, n):
		if x[i] > b[i]:
			if b[i] / x[i] < kmin:
				kmin = b[i] / x[i]
	sum = 0
	for i in range(n):
		x[i] *= kmin
		sum += x[i]
	if sum > v:
		sum = v
	print(sum)


(n, v) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = 1000000
for i in range(n):
	m = min(m, b[i] / a[i])
c = 0
for i in range(n):
	c += m * a[i]
print(min(c, v))


def mi():
	return map(int, input().split())
(n, v) = mi()
a = list(mi())
b = list(mi())
x = 100000
for i in range(n):
	x = min(x, b[i] / a[i])
print(min(sum(a) * x, v))


line = input()
lis = line.split()
n = int(lis[0])
v = int(lis[1])
line = input()
pro = line.split()
pro = [int(i) for i in pro]
line = input()
inc = line.split()
inc = [int(i) for i in inc]
x = None
for i in range(n):
	r = inc[i] / pro[i]
	if x is None or r < x:
		x = r
tot = 0
for i in pro:
	tot = tot + i * x
print(min(tot, v))


(n, V) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
answer = [V]
sum_of_proportions = sum(a)
for i in range(n):
	answer.append(b[i] / a[i] * sum_of_proportions)
print(min(answer))


(n, v) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
minm = b[0] / a[0]
for i in range(1, n):
	minm = min(minm, b[i] / a[i])
s = sum(a)
print(min(v, s * minm))


import math
(n, V) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
nb_soup = min([b[i] / a[i] for i in range(n)])
sa = sum(a)
print(min(nb_soup * sa, V))


(n, V) = input().split()
(n, V) = (int(n), int(V))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ratio = 100000
for i in range(n):
	ratio = min(ratio, b[i] / a[i])
suma = 0
for i in range(n):
	suma += ratio * a[i]
print(min(V, suma))


I = lambda : map(int, input().split())
(n, v) = map(int, input().split())
(a, b, q) = ([*I()], [*I()], 0)
import math
for i in a:
	q = math.gcd(q, i)
for i in range(n):
	a[i] //= q
	b[i] = b[i] / a[i]
print(min(min(b) * sum(a), v))