The worlds most successful thief Albert Spaggiari was planning for his next heist on the world bank. He decides to carry a sack with him, which can carry a maximum weight of C kgs. Inside the world bank there were N large blocks of gold. All the blocks have some profit value associated with them i.e. if he steals i^{th} block of weight w[i] then he will have p[i] profit. As blocks were heavy he decided to steal some part of them by cutting them with his cutter.
The thief does not like symmetry, hence, he wishes to not take blocks or parts of them whose weight is a perfect square. Now, you need to find out the maximum profit that he can earn given that he can only carry blocks of gold in his sack. 
Note: The answer should be precise upto 3 decimal places.
Example 1 :
N = 3, C = 10
w[] = {4, 5, 7}
p[] = {8, 5, 4)
Output: 
7.857
Explanation: As first blocks weight is 4
which is a perfect square, he will not use 
this block. Now with the remaining blocks 
the most optimal way is to use 2^{nd} block 
completely and cut 5kg piece from the 3^{rd} 
block to get a total profit of 5 + 2.857 
= 7.857
Your Task:
You don't need to read or print anything. Your task is to complete the function maximumProfit() which takes N, C, w[ ] and p[ ] as input parameters and returns the maximum profit thief can achieve with precision upto 3 decimal places.
Expected Time Complexity: O(N * LogN)
Expected Space Complexity : O(N)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ C ≤ 10^{18}
1 ≤ W_{i }≤ 10^{9}
1 ≤ P_{i }≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Greedy algorithms

Starter code: #User function Template for python3



class Solution:

	def maximumProfit(self, N, C, w, p):

		# Code here

Solutions:
class Solution:

	def maximumProfit(self, N, C, w, p):
		arr = sorted([(pi / wi, wi, pi) for (wi, pi) in zip(w, p)], reverse=True)
		ans = 0
		for (ri, wi, pi) in arr:
			if not int(wi ** 0.5) == wi ** 0.5:
				if C > wi:
					ans += pi
					C -= wi
				else:
					ans += round(C * ri, 3)
					break
		return ans


class Solution:

	def maximumProfit(self, N, C, w, p):
		a = [(w[i], p[i]) for i in range(N) if int(w[i] ** 0.5 + 0.5) ** 2 != w[i]]
		a.sort(key=lambda x: -x[1] / x[0])
		gain = 0
		for (we, pr) in a:
			if C > we:
				gain += pr
				C -= we
			else:
				gain += C / we * pr
				return gain
		return gain


class Solution:

	def maximumProfit(self, N, C, w, p):
		ratios = sorted([[P / W, W, P] for (W, P) in zip(w, p) if W ** (1 / 2) != int(W ** (1 / 2))], reverse=True)
		sm = 0
		for (R, W, P) in ratios:
			if C > W:
				sm += P
				C -= W
			else:
				sm += round(C * R, 3)
				break
		return sm


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		wp = list(zip(w, p))
		wp = [(p / w, w, p) for (w, p) in wp]
		wp = sorted(wp, key=lambda x: -x[0])
		t = 0
		for (d, w, p) in wp:
			if not math.sqrt(w).is_integer():
				if w < C:
					C -= w
					t += p
				else:
					t += round(C / w * p, 3)
					C = 0
		return t


class Solution:

	def maximumProfit(self, N, C, w, p):
		arr = []
		for i in range(N):
			arr.append([w[i], p[i]])
		arr.sort(key=lambda x: x[0] / x[1])
		i = 0
		profit = 0
		while C != 0 and i < N:
			if not (arr[i][0] ** 0.5).is_integer():
				if arr[i][0] <= C:
					profit += arr[i][1]
					C -= arr[i][0]
					i += 1
				else:
					profit += C * (arr[i][1] / arr[i][0])
					C = 0
					i += 1
			else:
				i += 1
		return profit


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		blocks = [[w[i], p[i], p[i] / w[i]] for i in range(N)]
		for i in range(N):
			if math.sqrt(blocks[i][0]) == int(math.sqrt(blocks[i][0])):
				blocks[i] = [0, 0, 0]
		blocks.sort(key=lambda x: x[2], reverse=True)
		profit = 0
		i = 0
		while True:
			if blocks[i][0] > C:
				return profit + C * blocks[i][2]
			profit += blocks[i][1]
			C -= blocks[i][0]
			i += 1
			if i == n:
				return profit


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		l = []
		for i in range(N):
			l.append([p[i] / w[i], p[i], w[i]])
		l.sort(reverse=True)
		s = 0
		for i in range(N):
			f = math.sqrt(l[i][2])
			if f.is_integer():
				continue
			elif l[i][2] < C:
				s = s + l[i][1]
				C = C - l[i][2]
			else:
				s = s + round(l[i][1] * (C / l[i][2]), 3)
				break
		return s


class Solution:

	def maximumProfit(self, N, c, w, p):
		ans = []
		for i in range(N):
			if w[i] ** 0.5 != int(w[i] ** 0.5):
				ans.append([p[i] / w[i], w[i], p[i]])
		ans.sort(reverse=True)
		i = 0
		final = 0
		while i < len(ans) and c != 0:
			temp = ans[i]
			if c >= temp[1]:
				final += temp[2]
				c -= temp[1]
				i += 1
			else:
				final += c * temp[0]
				c = 0
				i += 1
		return final


from math import sqrt

class Solution:

	def maximumProfit(self, N, C, w, p):
		arr = sorted([(pi / wi, wi, pi) for (wi, pi) in zip(w, p)], reverse=True)
		ans = 0
		for (ri, wi, pi) in arr:
			if not sqrt(wi).is_integer():
				if C > wi:
					ans += pi
					C -= wi
				else:
					ans += round(C * ri, 3)
					break
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, C) = input().split()
		n = int(n)
		C = int(C)
		temp = list(map(int, input().split()))
		w = []
		p = []
		for i in range(2 * n):
			if i % 2 == 0:
				w.append(temp[i])
			else:
				p.append(temp[i])
		ob = Solution()
		ans = ob.maximumProfit(n, C, w, p)
		print('{:.3f}'.format(ans))


from math import sqrt

class Solution:

	def maximumProfit(self, N, C, w, p):
		wp = list(zip(w, p))
		wp = [(p / w, w, p) for (w, p) in wp]
		wp = sorted(wp, key=lambda x: -x[0])
		total_p = 0
		for (d, w, p) in wp:
			if not sqrt(w).is_integer():
				if w < C:
					C -= w
					total_p += p
				else:
					total_p += round(C / w * p, 3)
					C = 0
		return total_p
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, C) = input().split()
		n = int(n)
		C = int(C)
		temp = list(map(int, input().split()))
		w = []
		p = []
		for i in range(2 * n):
			if i % 2 == 0:
				w.append(temp[i])
			else:
				p.append(temp[i])
		ob = Solution()
		ans = ob.maximumProfit(n, C, w, p)
		print('{:.3f}'.format(ans))


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		arr = list(zip(w, p))
		arr.sort(key=lambda x: x[0] / x[1])
		res = 0
		for i in arr:
			if C == 0:
				break
			if math.ceil(math.sqrt(i[0])) == math.floor(math.sqrt(i[0])):
				continue
			elif C >= i[0]:
				C -= i[0]
				res += i[1]
			else:
				res += round(i[1] / i[0] * C, 3)
				break
		return res


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		p_w = {}
		for i in range(N):
			try:
				a = p[i] / w[i]
			except:
				p_w[0] = [p[i], w[i]]
			p_w[a] = [p[i], w[i]]
		P = 0
		for i in reversed(sorted(p_w.keys())):
			if C > 0 and p_w[i][1] < C:
				sr = int(math.sqrt(p_w[i][1]))
				if sr * sr == p_w[i][1]:
					continue
				C = C - p_w[i][1]
				P += p_w[i][0]
			elif C > 0:
				sr = int(math.sqrt(p_w[i][1]))
				if sr * sr == p_w[i][1]:
					continue
				P += i * C
				C = 0
		return P


import math

class Solution:

	def maximumProfit(self, n, m, w, p):
		items = []
		for i in range(n):
			items.append([p[i], w[i]])
		items = sorted(items, key=lambda item: item[0] / item[1], reverse=True)
		profit = 0
		for i in range(n):
			(pro, wei) = items[i]
			ceil = math.ceil(math.sqrt(wei))
			floor = math.floor(math.sqrt(wei))
			if ceil != floor:
				if wei > m:
					f = m / wei
					pi = f * pro
					profit += pi
					break
				else:
					m -= wei
					profit += pro
		return profit


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		arr = []
		for i in range(n):
			if p[i] != 0:
				arr.append([w[i], p[i], w[i] / p[i]])
			else:
				arr.append([w[i], p[i], 999999999])
		arr.sort(key=lambda x: x[2])
		ans = 0
		for i in range(n):
			if C == 0:
				break
			if math.sqrt(arr[i][0]) % 1 == 0:
				continue
			if C >= arr[i][0]:
				C -= arr[i][0]
				ans += arr[i][1]
			else:
				ans += arr[i][1] / arr[i][0] * C
				break
		return ans


class Solution:

	def perfectSquare(self, n):
		import math
		s = int(math.sqrt(n))
		if s * s == n:
			return True
		else:
			return False

	def maximumProfit(self, N, C, w, p):
		(w, p) = zip(*sorted(zip(w, p), key=lambda item: item[1] / item[0], reverse=True))
		profit = 0
		for i in range(N):
			check = self.perfectSquare(w[i])
			if check == False:
				if C > w[i]:
					C -= w[i]
					profit += p[i]
				else:
					per_unit_cost = p[i] / w[i]
					total_cost = per_unit_cost * C
					profit += total_cost
					C = 0
					break
		return profit


class Solution:

	def maximumProfit(self, N, C, w, p):
		naj = []
		i = 0
		while i < len(w):
			if w[i] ** 0.5 % 1 == 0:
				w.pop(i)
				p.pop(i)
				izbacen = True
			else:
				naj.append([w[i], p[i]])
				i += 1
		naj.sort(reverse=True, key=lambda x: x[1] / x[0])
		nap = 0.0
		vr = 0.0
		i = 0
		C = float(C)
		while i < len(naj):
			if naj[i][0] <= C - nap:
				vr += naj[i][1]
				nap += naj[i][0]
			elif nap < C:
				vr += (C - nap) * naj[i][1] / naj[i][0]
				nap += C - nap
			else:
				break
			i += 1
		return vr


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		l = [[p[i] / w[i], p[i], w[i]] for i in range(len(w)) if int(math.sqrt(w[i])) ** 2 != w[i]]
		l.sort(reverse=True)
		pro = 0
		i = 0
		while i < len(l) and C - l[i][2] > 0:
			pro += l[i][1]
			C -= l[i][2]
			i += 1
		pro += C * l[i][1] / l[i][2]
		return pro


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		d = {}
		pro = 0
		for i in range(N):
			if w[i] != 0:
				d[p[i] / w[i]] = w[i]
		d1 = sorted(d, reverse=True)
		for i in d1:
			if C > 0:
				sq = math.sqrt(d[i])
				if sq == int(sq):
					pass
				elif C < d[i]:
					pro += C * i
					C = 0
					break
				else:
					C -= d[i]
					pro += i * d[i]
		return pro


from math import sqrt

class Solution:

	def maximumProfit(self, N, C, w, p):
		pw = []
		for i in range(N):
			if int(sqrt(w[i])) * int(sqrt(w[i])) != w[i]:
				pw.append([p[i], w[i]])
		pw.sort(key=lambda x: -(x[0] / x[1]))
		ans = 0
		for i in range(N):
			if C - pw[i][1] >= 0:
				C -= pw[i][1]
				ans += pw[i][0]
			else:
				ans += C * (pw[i][0] / pw[i][1])
				break
		return ans


import math

def squ(x):
	if x >= 0:
		sr = int(math.sqrt(x))
		return sr * sr == x

class Solution:

	def maximumProfit(self, N, C, w, p):
		activity = []
		for i in range(N):
			if w[i] != 0:
				activity.append([w[i], p[i], p[i] / w[i]])
		activity.sort(key=lambda x: x[2], reverse=True)
		ans = 0
		for act in activity:
			if squ(act[0]) == True:
				continue
			else:
				k = act[1]
				if act[0] < C and C > 0:
					ans += k
					C -= act[0]
				elif C > 0:
					a = act[1] / act[0] * C
					ans += a
					break
		return ans


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		V = []
		for i in range(N):
			temp = int(math.sqrt(w[i]))
			if temp * temp != w[i]:
				V.append([p[i] / w[i], w[i], p[i]])
		V.sort(reverse=True)
		cost = 0
		for i in range(len(V)):
			if C >= V[i][1]:
				C -= V[i][1]
				cost += V[i][2]
			else:
				cost += C * V[i][0]
				break
		return cost


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		for i in range(N):
			t = int(math.sqrt(w[i]))
			if t * t == w[i]:
				p[i] = 0
		perunit = []
		for i in range(N):
			if p[i] == 0:
				perunit.append([0, i])
			else:
				x = p[i] / w[i]
				perunit.append([x, i])
		perunit.sort(reverse=True)
		i = 0
		res = 0
		while i < N and C > 0:
			idx = perunit[i][1]
			pft = perunit[i][0]
			cw = min(C, w[idx])
			res += cw * pft
			C -= cw
			i += 1
		return res


import math

class Solution:

	def maximumProfit(self, N, W, w, p):
		d = {}
		for i in range(N):
			try:
				a = p[i] / w[i]
			except:
				d[0] = [p[i], w[i]]
			d[a] = [p[i], w[i]]
		p = 0
		for i in reversed(sorted(d.keys())):
			if W > 0 and d[i][1] < W:
				root = int(math.sqrt(d[i][1]))
				if root * root == d[i][1]:
					continue
				p += d[i][0]
				W -= d[i][1]
			else:
				root = int(math.sqrt(d[i][1]))
				if root * root == d[i][1]:
					continue
				p += i * W
				W = 0
				break
		return p


import math

class Solution:

	def maximumProfit(self, n, c, w, p):
		ar = []
		pro = 0
		for i in range(n):
			try:
				ar.append([p[i] / w[i], w[i], p[i]])
			except:
				ar.append([0, w[i], p[i]])
		ar.sort(reverse=True)
		for i in range(n):
			(ra, we, pr) = ar[i]
			m = int(math.sqrt(we))
			if int(m * m) == we:
				continue
			if c > 0 and c >= we:
				c -= we
				pro += pr
			elif c > 0:
				pro += ra * c
				c = 0
		return pro


import math
import collections

class Solution:

	def maximumProfit(self, N, C, w, p):
		arr = {}
		for i in range(N):
			temp = math.sqrt(w[i])
			if int(temp) != temp:
				arr[p[i] / w[i]] = i
			else:
				w[i] = -1
		arr = collections.OrderedDict(sorted(arr.items(), reverse=True))
		final = 0
		for i in arr:
			ind = arr[i]
			if C <= w[ind]:
				final += C * i
				break
			else:
				final += i * w[ind]
				C -= w[ind]
		return final


import math

class Solution:

	def isPerfectSq(self, x):
		sq = int(math.sqrt(x))
		return sq * sq == x

	def maximumProfit(self, N, C, w, p):
		profit = 0
		for i in sorted(zip(w, p), key=lambda x: -x[1] / x[0] if x[0] > 0 else x[1]):
			if self.isPerfectSq(i[0]):
				continue
			if i[0] <= C:
				profit += i[1]
				C -= i[0]
			else:
				profit += i[1] / i[0] * C
				break
		return profit


import math

class sack:

	def __init__(self, weight=0, profit=0):
		self.weight = weight
		self.profit = profit

class Solution:

	def maximumProfit(self, N, C, w, p):
		temp = []
		for i in range(0, N):
			temp.append(sack(w[i], p[i]))
		temp.sort(key=lambda x: x.profit / x.weight if x.weight > 0 else x.profit, reverse=True)
		ans = 0
		for i in temp:
			if C == 0:
				break
			if math.sqrt(i.weight).is_integer():
				continue
			if i.weight <= C:
				ans += i.profit
				C -= i.weight
			else:
				ans += i.profit / i.weight * C
				C = 0
		return ans


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		z = []
		count = 0
		for i in range(N):
			if w[i] != 0:
				z.append((w[i], p[i], float(p[i]) / float(w[i])))
		z.sort(key=lambda x: x[2], reverse=True)
		for i in z:
			if C == 0:
				break
			if int(math.sqrt(i[0])) * int(math.sqrt(i[0])) != i[0]:
				if i[0] <= C:
					count += i[1]
					C -= i[0]
				else:
					count += i[2] * C
					C = 0
		return count


class Solution:

	def maximumProfit(self, N, C, w, p):
		l = []
		for i in range(N):
			if w[i] != 0:
				l.append((p[i], w[i]))
		l.sort(key=lambda x: x[0] / x[1], reverse=True)
		prof = 0
		for i in l:
			if self.isperf(i[1]):
				continue
			elif C - i[1] >= 0:
				C -= i[1]
				prof += i[0]
				if C == 0:
					return prof
			else:
				fractn = C / i[1]
				prof += i[0] * fractn
				return prof
		return 9.9

	def isperf(self, num):
		if num ** 0.5 == int(num ** 0.5):
			return True


import math

class Solution:

	def isPerfectSquare(self, x):
		if x >= 0:
			sr = int(math.sqrt(x))
			return sr * sr == x
		return false

	def maximumProfit(self, N, C, w, p):
		temp = []
		ans = 0
		for i in range(N):
			if not self.isPerfectSquare(w[i]):
				temp.append([p[i] / w[i], p[i], w[i]])
		temp.sort(key=lambda x: x[0], reverse=True)
		i = 0
		while C:
			if temp[i][2] <= C:
				ans += temp[i][1]
				C -= temp[i][2]
			else:
				ans += temp[i][1] * C / temp[i][2]
				break
			i += 1
		return ans


import math

class Solution:

	def isPerfectSquare(self, x):
		if x >= 0:
			sr = int(math.sqrt(x))
			return sr * sr == x
		return false

	def maximumProfit(self, N, c, w, p):
		arr = []
		for i in range(n):
			if p[i] != 0:
				arr.append([w[i], p[i], w[i] / p[i]])
			else:
				arr.append([w[i], p[i], 999999999])
		arr.sort(key=lambda x: x[2])
		ans = 0
		for i in range(n):
			if c == 0:
				break
			if math.sqrt(arr[i][0]) % 1 == 0:
				continue
			if c >= arr[i][0]:
				c -= arr[i][0]
				ans += arr[i][1]
			else:
				ans += arr[i][1] / arr[i][0] * c
				break
		return ans


import math

class Solution:

	def isSquare(self, N):
		if N >= 0:
			s = int(math.sqrt(N))
			if s * s == N:
				return True
		return False

	def maximumProfit(self, N, C, w, p):
		d = dict()
		for i in range(N):
			if self.isSquare(w[i]) == False:
				r = p[i] / w[i]
				d[r] = i
		l = list(d.items())
		l.sort(key=lambda x: x[0], reverse=True)
		wt = 0
		pr = float(0)
		for i in range(len(l)):
			if wt + w[l[i][1]] > C:
				pr = pr + (C - wt) * p[l[i][1]] / w[l[i][1]]
				wt += C - wt
				return pr
			if wt == C:
				return pr
			else:
				pr += p[l[i][1]]
				wt += w[l[i][1]]
		return pr
		return 0


class Solution:

	def maximumProfit(self, N, C, w, p):
		from math import sqrt
		h = 0
		s = 0
		a = []
		for i in range(N):
			if p[i] != 0:
				a.append((w[i] / p[i], i))
			else:
				a.append((999999999, i))
		a.sort()
		for i in range(N):
			g = int(sqrt(w[a[i][1]]))
			if g * g == w[a[i][1]]:
				continue
			elif w[a[i][1]] <= C:
				C = C - w[a[i][1]]
				s = s + p[a[i][1]]
			else:
				s = s + C / w[a[i][1]] * p[a[i][1]]
				break
		s = round(s, 3)
		return s


import math

class Solution:

	def check(self, num):
		x = math.sqrt(num)
		if x * x == num:
			return True
		return False

	def maximumProfit(self, N, c, w, p):
		arr = []
		for i in range(n):
			if p[i] != 0:
				arr.append([w[i], p[i], w[i] / p[i]])
			else:
				arr.append([w[i], p[i], 999999999])
		arr.sort(key=lambda x: x[2])
		ans = 0
		for i in range(n):
			if c == 0:
				break
			if math.sqrt(arr[i][0]) % 1 == 0:
				continue
			if c >= arr[i][0]:
				c -= arr[i][0]
				ans += arr[i][1]
			else:
				ans += arr[i][1] / arr[i][0] * c
				break
		return ans


def isSquare(n):
	x = int(pow(n, 0.5))
	return n in (x * x, pow(x + 1, 2), pow(x - 1, 2))

class Solution:

	def maximumProfit(self, N, C, w, p):
		arr = sorted([(i, j) for (i, j) in zip(w, p) if not isSquare(i)], reverse=True, key=lambda x: x[1] / x[0])
		i = ans = 0
		n = len(arr)
		while i < n and C > 0:
			curr = min(C, arr[i][0])
			ans += curr * (arr[i][1] / arr[i][0])
			C -= curr
			i += 1
		return ans


class Solution:

	def isPerfectSquare(self, x):
		left = 1
		right = x
		while left <= right:
			mid = (left + right) // 2
			if mid * mid == x:
				return True
			elif mid * mid > x:
				right = mid - 1
			elif mid * mid < x:
				left = mid + 1
		return False

	def maximumProfit(self, N, C, w, p):
		arr = []
		for i in range(N):
			if w[i] == 0:
				arr.append((w[i], p[i], 0))
			else:
				arr.append((w[i], p[i], p[i] / w[i]))
		arr.sort(key=lambda x: x[2], reverse=True)
		sum = 0
		for i in range(N):
			if C == 0:
				break
			if self.isPerfectSquare(arr[i][0]):
				continue
			elif C >= arr[i][0]:
				sum += arr[i][1]
				C -= arr[i][0]
			else:
				sum += arr[i][2] * C
				break
		return sum


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		l = []
		profit = 0
		for i in range(N):
			if w[i] != 0:
				x = p[i] / w[i]
			else:
				x = 0
			l.append([x, p[i], w[i]])
		l.sort()
		l = l[::-1]
		for i in l:
			temp = i[2]
			temp = math.sqrt(temp)
			if temp != int(temp):
				if i[2] <= C:
					profit += i[1]
					C -= i[2]
				else:
					profit += C * i[1] / i[2]
					break
		profit = round(profit, 3)
		return profit


import math

class Solution:

	def maximumProfit(self, n, c, w, p):
		l = []

		def check(t):
			v = math.sqrt(t)
			if int(v) == math.ceil(v):
				return False
			return True
		for i in range(n):
			if check(w[i]):
				l.append((p[i] / w[i], p[i], w[i]))
		l.sort(reverse=True)
		ans = 0
		for i in l:
			if c > i[2]:
				c -= i[2]
				ans += i[1]
			else:
				ans += i[0] * c
				c = 0
		return round(ans, 3)


class Solution:

	def maximumProfit(self, N, C, w, p):
		l = [(p[i] / float(w[i]), i) for i in range(N) if w[i] != 0]
		l.sort(reverse=True)
		i = 0
		ans = 0

		def check(n):
			i = 1
			while i * i < n:
				i += 1
			return i * i == n
		while i < N:
			if check(w[l[i][1]]):
				i += 1
				continue
			if C >= w[l[i][1]]:
				ans += p[l[i][1]]
				C -= w[l[i][1]]
				i += 1
			else:
				ans += l[i][0] * C
				break
		return ans


from math import floor, sqrt
import heapq

class Solution:

	def maximumProfit(self, N, C, w, p):
		q = []
		max_profit = 0
		for val in range(N):
			if sqrt(w[val]) == int(sqrt(w[val])):
				continue
			heapq.heappush(q, (-p[val] / w[val], val))
		while C != 0 and len(q):
			(ratio, index) = heapq.heappop(q)
			ratio = -ratio
			if w[index] <= C:
				C -= w[index]
				max_profit += p[index]
			else:
				max_profit += round(ratio * C, 3)
				C = 0
		return max_profit


class Solution:

	def isPerfectSquare(self, n):
		x = n ** (1 / 2)
		if x == int(x):
			return True
		return False

	def maximumProfit(self, N, C, w, p):
		wp = []
		for i in range(N):
			wp.append([w[i], p[i]])
		remaining = C
		total = 0
		wp.sort(key=lambda x: x[1] / x[0] if x[0] != 0 else -1, reverse=True)
		for (wieght, price) in wp:
			if not self.isPerfectSquare(wieght):
				if wieght < remaining:
					total += price
					remaining -= wieght
				else:
					total += price * remaining / wieght
					remaining = 0
		return total


from math import sqrt

class Solution:

	def is_perfect_square(self, weight):
		sqrt_weight = int(sqrt(weight))
		return sqrt_weight * sqrt_weight == weight

	def maximumProfit(self, N, C, w, p):
		unit_profit_with_weight = []
		for idx in range(N):
			if not self.is_perfect_square(w[idx]):
				unit_profit_with_weight.append((p[idx] / w[idx], w[idx]))
		unit_profit_with_weight.sort()
		max_profit = 0.0
		capacity = C
		idx = len(unit_profit_with_weight) - 1
		while capacity > 0 and idx >= 0:
			part_taken = min(capacity, unit_profit_with_weight[idx][1])
			max_profit += part_taken * unit_profit_with_weight[idx][0]
			capacity -= part_taken
			idx -= 1
		return max_profit


class Solution:

	def maximumProfit(self, N, C, w, p):
		a = []
		resp = 0
		for i in range(N):
			if w[i] != 0:
				a.append([p[i], w[i], p[i] / w[i]])
		a.sort(key=lambda x: x[2], reverse=True)
		for i in range(N):
			b = a[i][1] ** 0.5
			if b - int(b) == 0:
				continue
			elif C - a[i][1] >= 0:
				resp += a[i][0]
				C -= a[i][1]
			elif C != 0:
				resp += a[i][0] * C / a[i][1]
				return resp
			else:
				return resp


from math import sqrt
import heapq

class Solution:

	def maximumProfit(self, N, C, w, p):
		useful_blocks = []
		heapq.heapify(useful_blocks)
		for i in range(len(w)):
			if sqrt(w[i]) % 1:
				heapq.heappush(useful_blocks, (-p[i] / w[i], w[i], p[i]))
		resulting_profit = 0
		resulting_weight = 0
		while resulting_weight < C and useful_blocks:
			(_, weight, profit) = heapq.heappop(useful_blocks)
			if weight < C - resulting_weight:
				resulting_weight += weight
				resulting_profit += profit
			else:
				resulting_profit += profit / weight * (C - resulting_weight)
				break
		return resulting_profit


import math

class Solution:

	def maximumProfit(self, N, C, w, p):
		arr = []
		for i in range(N):
			if w[i] != 0:
				arr.append([w[i], p[i], p[i] / w[i]])
		arr.sort(key=lambda x: x[2], reverse=True)
		ans = 0
		for i in range(N):
			x = math.sqrt(arr[i][0])
			if x - int(x) != 0:
				if C - arr[i][0] > 0:
					ans += arr[i][1]
					C -= arr[i][0]
				else:
					ans += arr[i][1] / arr[i][0] * C
					return ans
		return ans


class Solution:

	def is_sqrt(self, num):
		a = int(num ** 0.5)
		if a ** 2 == num:
			return True
		return False

	def maximumProfit(self, N, C, w, p):
		ar = []
		for i in range(N):
			if p[i] != 0:
				ar.append([w[i], p[i], w[i] / p[i]])
		ar.sort(key=lambda x: x[2])
		ans = [0, 0]
		for i in range(N):
			if not self.is_sqrt(ar[i][0]):
				if ans[0] + ar[i][0] > C:
					val = ar[i][1] / ar[i][0]
					v = C - ans[0]
					ans[1] += v * val
					return ans[1]
				else:
					ans[0] += ar[i][0]
					ans[1] += ar[i][1]


from math import sqrt

class Solution:

	def maximumProfit(self, N, C, w, p):
		c = []
		for i in range(N):
			if sqrt(w[i]) != int(sqrt(w[i])):
				c.append([p[i] / w[i], w[i]])
		c.sort(reverse=True)
		profit = 0
		weight = 0
		for i in c:
			if i[1] + weight > C:
				profit += i[0] * (C - weight)
				weight += C - weight
			else:
				profit += i[0] * i[1]
				weight += i[1]
			if weight == C:
				break
		return profit


class Solution:

	def maximumProfit(self, N, C, w, p):
		a = []
		prof = 0
		for i in range(N):
			if w[i] == 0:
				continue
			else:
				a += ((w[i], p[i]),)
		i = 0
		a = sorted(a, key=lambda p: p[1] / p[0], reverse=True)
		while C > 0 and i < N:
			p = int(a[i][0] ** 0.5)
			if p * p == a[i][0]:
				i += 1
				continue
			if C - a[i][0] >= 0:
				prof += a[i][1]
				C -= a[i][0]
			else:
				p = int(C ** 0.5)
				if p * p != C:
					prof += a[i][1] / a[i][0] * C
					break
				else:
					i += 1
					continue
			i += 1
		return prof