Nathan is preparing for the Dash marathon. He has N training plans. The i-th plan has an effectiveness of A_{i}, but requires that at least B_{i} other training plans must be performed before it. A training plan cannot be repeated. 

If he performs some K > 0 distinct trainings - P_{1}, P_{2}, \ldots , P_{K} (1 ≤ P_{i} ≤ N, P_{i} \neq P_{j}) then his training score is \frac{\sum_{j=1}^{K} A_{P_{j}}}{K}. If Nathan does not perform any training plan (K = 0), then his score is 0.

What is the highest score that Nathan can get by performing zero or more training plans, if he can perform them in any order?

------ Input Format ------ 

- The first line of the input contains a single integer T - the number of test cases. The description of T test cases follows.
- The first line of each test case contains N - the number of training plans.
- The second line contains N integers A_{1}, A_{2}, \ldots, A_{N} where A_{i} is the effectiveness of the i-th training plan.
- The third line contains N integers B_{1}, B_{2}, \ldots, B_{N} where B_{i} is the number of pre-requisite training plans for the i-th training plan.

------ Output Format ------ 

- For each test case, output a single real number - the highest score that Nathan can get by performing zero or more training plans.
- Your answer is considered correct if its absolute or relative error does not exceed 10^{-6}.
Formally, let your answer be X, and the jury's answer be Y. Your answer is accepted if and only if \frac{|X - Y|}{\max{(1, |Y|)}} ≤ 10^{-6}.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$-10^{5} ≤ A_{i} ≤ 10^{5}$
$0 ≤ B_{i} ≤ N - 1$
- Sum of $N$ over all test cases does not exceed $5\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
-9 -21 -4 -43
0 0 0 0
5
10 14 5 9 1
4 1 3 0 0
7
-1 101 5 63 -7 -88 59
0 1 6 2 3 4 5

----- Sample Output 1 ------ 
0.000000
11.500000
54.333333
----- explanation 1 ------ 
Test case 1: It is optimal for Nathan to not perform any training plans as all the plans have negative $A_{i}$ value.

Test case 2: It is optimal for Nathan to:
- First, perform the $4$-th training plan (for which $B_{i} = 0$).
- Then perform the $2$-nd training plan (for which $B_{i} = 1$ which is satisfied as he has already performed $1$ training plan)

Test case 3: It is optimal for Nathan to:
- First, perform the $1$-st training plan (for which $B_{i} = 0$).
- Then perform the $2$-nd training plan (for which $B_{i} = 1$ which is satisfied as he has already performed $1$ training plan)
- Then perform the $4$-th training plan (for which $B_{i} = 2$ which is satisfied as he has already performed $2$ training plans)

Source: codechef | Difficulty: HARD
Tags: Data structures

Greedy algorithms


Solutions:
import heapq
for _ in range(int(input())):
	number = int(input())
	eff = list(map(int, input().split()))
	b = list(map(int, input().split()))
	heap = []
	tempheap = []
	ans = 0
	realans = [0.0]
	k = 1
	for i in range(number):
		heapq.heappush(heap, [b[i], eff[i]])
	condition1 = True
	while tempheap or (condition1 and heap[0][0] < k):
		condition = True
		if not heap:
			condition = False
		while condition and heap[0][0] == k - 1:
			mn = heapq.heappop(heap)
			heapq.heappush(tempheap, [-mn[1], mn[0]])
			if not heap:
				condition = False
		if not heap:
			condition1 = False
		m = heapq.heappop(tempheap)
		ans = ans + -m[0]
		realans.append(ans / k)
		k += 1
	print(max(realans))


from heapq import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = []
	for _ in range(n):
		arr.append([])
	for (x, y) in zip(a, b):
		arr[y].append(x)
	heap = []
	score = 0
	sm = 0
	ni = 0
	i = 0
	while i < n:
		for task in arr[i]:
			heappush(heap, -task)
		if len(heap) == 0:
			break
		val = -heappop(heap)
		sm += val
		ni += 1
		score = max(score, sm / ni)
		i += 1
	print(score)


import sys, os.path
if os.path.exists('input.txt'):
	sys.stdout = open('output.txt', 'w')
	sys.stdin = open('input.txt', 'r')

def solve(n, eff, preq):
	from heapq import heapify, heappop as pop, heappush as push
	tasks = {}
	for (e, p) in zip(eff, preq):
		tasks[p] = tasks.get(p, [])
		tasks[p].append(e)
	if 0 not in tasks:
		return 0
	res = 0
	total = 0
	done = 0
	heap = [-val for val in tasks[0]]
	heapify(heap)
	while heap:
		val = -pop(heap)
		total += val
		done += 1
		res = max(res, total / done)
		if done in tasks:
			for x in tasks[done]:
				push(heap, -x)
	return res

def main():
	sys.setrecursionlimit(10 ** 8)
	for _ in range(int(input())):
		n = int(input())
		eff = [int(val) for val in input().split()]
		preq = [int(val) for val in input().split()]
		result = solve(n, eff, preq)
		print(result)
main()


import heapq
t = int(input())
for _ in range(t):
	pq = []
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	crr = []
	for _ in range(n):
		crr.append([])
	for i in range(n):
		(a, b) = (arr[i], brr[i])
		crr[b].append(a)
	ans = 0
	sumation = 0
	for i in range(n):
		for val in crr[i]:
			heapq.heappush(pq, -val)
		if len(pq) == 0:
			break
		sumation -= heapq.heappop(pq)
		if sumation / (i + 1) > ans:
			ans = sumation / (i + 1)
	print(ans)


import heapq
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = [[] for i in range(n)]
	for i in range(n):
		arr[b[i]].append(a[i])
	ans = 0
	sum = 0
	heap = []
	for i in range(n):
		for j in arr[i]:
			heapq.heappush(heap, -j)
		if not heap:
			break
		sum += -heapq.heappop(heap)
		ans = max(ans, sum / (i + 1))
	print(ans)


import heapq

def prepare_split_tasks(num, a1, a2):
	tasks = [[] for x in range(num)]
	for j in range(num):
		tasks[a2[j]].append(a1[j] * -1)
	return tasks
t = int(input().strip())
while t > 0:
	t -= 1
	n = int(input().strip())
	arr1 = list(map(int, input().strip().split()))
	arr2 = list(map(int, input().strip().split()))
	split_tasks = prepare_split_tasks(n, arr1, arr2)
	max_value = 0
	value = 0
	cnt = 0
	tasks_in_consideration = split_tasks[0]
	heapq.heapify(tasks_in_consideration)
	for i in range(n):
		if len(tasks_in_consideration) == 0:
			break
		task = heapq.heappop(tasks_in_consideration)
		value = value + task * -1
		cnt += 1
		if value / cnt > max_value:
			max_value = value / cnt
		if i < n - 1:
			for x in split_tasks[i + 1]:
				heapq.heappush(tasks_in_consideration, x)
	print(max_value)


from heapq import heappush, heappop
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	dic = {}
	for (i, a) in enumerate(A):
		if B[i] in dic:
			dic[B[i]].append(a)
		else:
			dic[B[i]] = [a]
	heap = []
	(sm, ans) = (0, 0)
	for i in range(N):
		if i in dic:
			for d in dic[i]:
				heappush(heap, -d)
		if not heap:
			break
		sm += -heappop(heap)
		ans = max(ans, sm / (i + 1))
	print(ans)


from heapq import heappush, heappop
for _ in range(int(input())):
	h = []
	totalA = 0
	bestAverage = 0
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	programs = [(a[i], b[i]) for i in range(n)]
	programs = sorted(programs, key=lambda x: x[1])
	numUsed = 0
	j = 0
	if programs[0][1] > 0:
		print(0)
		continue
	while True:
		while j < n:
			if programs[j][1] <= numUsed:
				heappush(h, -programs[j][0])
				j += 1
			else:
				break
		if h:
			nextProgram = -heappop(h)
			totalA += nextProgram
			numUsed += 1
			bestAverage = max(bestAverage, totalA / float(numUsed))
		else:
			break
	print(bestAverage)


from queue import PriorityQueue
q = PriorityQueue()
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	b = list(map(int, input().split()))
	for i in range(n):
		if b[i] not in d:
			d[b[i]] = [a[i]]
		else:
			d[b[i]].append(a[i])
	qu = PriorityQueue()
	s = 0
	ma = 0
	i = 0
	c = 0
	if 0 not in d:
		print(0)
	else:
		for j in d[i]:
			qu.put(-1 * j)
		while qu.qsize() > 0:
			s += -1 * qu.get()
			c += 1
			avg = s / c
			if avg > ma:
				ma = avg
			i += 1
			if i in d:
				for j in d[i]:
					qu.put(-1 * j)
		print(ma)


import heapq
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	dic = defaultdict(list)
	for i in range(n):
		dic[b[i]].append(a[i])
	count = 0
	last_push = -1
	l = []
	curr_max = 0
	mean = 0
	while count < n + 1:
		while last_push < count:
			last_push += 1
			for i in dic[last_push]:
				heapq.heappush(l, -1 * i)
		if len(l) == 0:
			break
		else:
			mean = mean * count + -1 * heapq.heappop(l)
			count += 1
			mean = mean / count
			curr_max = max(mean, curr_max)
	print(round(curr_max, 6))


from heapq import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().lstrip().split()))
	b = list(map(int, input().lstrip().split()))
	li = []
	for i in range(n):
		li.append([])
	for (x, y) in zip(a, b):
		li[y].append(x)
	heap = []
	i = 0
	score = 0
	total = 0
	count = 0
	while i < n:
		for j in li[i]:
			heappush(heap, -j)
		if len(heap) == 0:
			break
		val = -heappop(heap)
		score += val
		count += 1
		total = max(total, score / count)
		i += 1
	print(total)


import heapq
for _ in range(int(input())):
	N = int(input())
	Q = list(map(int, input().split()))
	R = list(map(int, input().split()))
	dic = {}
	for i in range(N):
		if R[i] in dic:
			dic[R[i]].append(Q[i])
		else:
			dic[R[i]] = [Q[i]]
	li = []
	mx = 0
	sm = 0
	cnt = 0
	idx = 0
	while True:
		if idx in dic:
			for i in dic[idx]:
				heapq.heappush(li, -i)
		idx += 1
		if len(li) == 0:
			break
		eff = -heapq.heappop(li)
		sm += eff
		cnt += 1
		mx = max(mx, sm / cnt)
	print(mx)


import heapq
for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	curr = list()
	heapq.heapify(curr)
	new = []
	for i in range(N):
		new.append((A[i], B[i]))

	def cmp(x):
		return x[-1]
	new.sort(key=cmp)
	j = 0
	ans = 0
	currans = 0
	for k in range(1, N + 1):
		while j < N and new[j][-1] < k:
			heapq.heappush(curr, -new[j][0])
			j += 1
		if len(curr) == 0:
			break
		currans += -heapq.heappop(curr)
		ans = max(ans, currans / k)
	print(ans)


import heapq as hp
test = int(input())
while test:
	n = int(input())
	a = input().split()
	b = input().split()
	c = []
	for i in range(n):
		c.append([])
	l = 0
	while l < n:
		c[int(b[l])].append(int(a[l]))
		l += 1
	heap = []
	hp.heapify(heap)
	ans = cthelp = 0
	count = 0
	for i in c:
		for k in i:
			hp.heappush(heap, -k)
		if len(heap) == 0:
			break
		else:
			count += 1
			cthelp += -1 * hp.heappop(heap)
		ans = max(ans, cthelp / count)
	print(ans)
	test -= 1


from heapq import *
T = int(input())
for t in range(T):
	n = int(input())
	A = [int(_) for _ in input().split()]
	B = [int(_) for _ in input().split()]
	arr = [[] for _ in range(n)]
	for i in range(n):
		arr[B[i]].append(A[i])
	heap = []
	i = addn = ans = 0
	while i < n:
		for task in arr[i]:
			heappush(heap, -task)
		if len(heap) == 0:
			break
		eff = -heappop(heap)
		addn += eff
		ans = max(ans, addn / (i + 1))
		i += 1
	print(ans)


import math
import bisect
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def process(A, B, N):
	Dict = ddc(list)
	for i in range(N):
		Dict[B[i]].append(A[i])
	Q = []
	(curr, done, Max) = (0, 0, 0)
	for i in range(N):
		for ele in Dict[i]:
			heapq.heappush(Q, -ele)
		if not Q:
			break
		curr += -heapq.heappop(Q)
		done += 1
		Max = max(Max, curr / done)
	return Max

def main():
	for _ in range(int(input())):
		N = intin()
		A = list(mapin())
		B = list(mapin())
		print(process(A, B, N))
main()


from collections import Counter, defaultdict, deque
import itertools
import re
import math
from functools import reduce
import operator
import bisect
import heapq
import functools
mod = 10 ** 9 + 7
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	tr = [[] for _ in range(n)]
	for i in range(n):
		tr[b[i]].append(a[i])
	ans = 0
	su = 0
	heap = []
	for i in range(n):
		for j in tr[i]:
			heapq.heappush(heap, -j)
		if not heap:
			break
		su += -heapq.heappop(heap)
		ans = max(ans, su / (i + 1))
	print(ans)


import heapq
for _ in range(int(input())):
	numberOfSessions = int(input())
	efficiencySessionList = list(map(int, input().split()))
	sessionsRequiredList = list(map(int, input().split()))
	mappedEfficiencyRequired = [(sessionsRequiredList[i], i) for i in range(numberOfSessions)]
	mappedEfficiencyRequired.sort(reverse=True)
	heap = []
	highestScore = sumVal = 0
	for minK in range(numberOfSessions):
		while mappedEfficiencyRequired and mappedEfficiencyRequired[-1][0] <= minK:
			index = mappedEfficiencyRequired[-1][1]
			mappedEfficiencyRequired.pop()
			heapq.heappush(heap, -efficiencySessionList[index])
		if heap:
			sumVal += -heapq.heappop(heap)
			highestScore = max(highestScore, sumVal / (minK + 1))
		else:
			break
	print('{:.6f}'.format(highestScore))


import heapq
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	nums = sorted(zip(b, a))
	heap = []
	(ans, temp, count) = (0.0, 0, 0)
	(i, j) = (0, 0)
	while j < n:
		while i < n and nums[i][0] <= j:
			heapq.heappush(heap, -1 * nums[i][1])
			i += 1
		if heap:
			temp += -1 * heapq.heappop(heap)
			count += 1
			ans = max(ans, temp / count)
			j += 1
		else:
			break
	print('%.6f' % ans)


import heapq
import numpy as np
tc = int(input())
while tc:
	tc -= 1
	n = int(input())
	A = np.array(list(map(float, input().strip().split())))
	B = np.array(list(map(int, input().strip().split())))
	arr = [[] for _ in range(n)]
	for (a, b) in zip(A, B):
		arr[b].append(a)
	li = []
	i = 0
	score = 0
	sm = 0
	ni = 0
	while i < n:
		for k in arr[i]:
			heapq.heappush(li, -k)
		if len(li) == 0:
			break
		v = -heapq.heappop(li)
		sm += v
		ni += 1
		score = max(score, sm / ni)
		i += 1
	print(score)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr):
	max_sum = float('-inf')
	max_cur = 0
	for num in ar:
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def hfc(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, b % a)

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def solve(t):
	n = readInts()
	ar1 = readList()
	ar2 = readList()
	dic = {}
	k = 0
	res = 0
	for i in range(n):
		num = ar2[i]
		if num in dic:
			dic[num].append(ar1[i])
		else:
			dic[num] = [ar1[i]]
	heap = []
	heapify(heap)
	max_sum = 0
	for i in range(n):
		if i in dic and len(dic[i]) > 0:
			for task in dic[i]:
				heappush(heap, -task)
		if len(heap) == 0:
			break
		max_sum += -heappop(heap)
		k += 1
		res = max(res, max_sum / k)
	print(res)

def main():
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


from heapq import heappush, heappop
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	heap = []
	(tc, ti, res) = (0, 0, 0)
	for _ in range(n):
		l.append([])
	for (x, y) in zip(a, b):
		l[y].append(x)
	for i in range(n):
		for j in l[i]:
			heappush(heap, -j)
		if len(heap) == 0:
			break
		tc += -heappop(heap)
		ti += 1
		res = max(res, tc / ti)
	print(res)


from collections import defaultdict
import heapq
import math
from math import sqrt
for _ in range(int(input())):
	d = defaultdict(list)
	n = int(input())
	l = list(map(int, input().split()))
	p = list(map(int, input().split()))
	for i in range(n):
		d[p[i]].append(l[i])
	h = []
	s = 0
	for i in d[s]:
		heapq.heappush(h, -1 * i)
	ans = 0
	maxi = -1 * float('inf')
	while h:
		s += 1
		ans += -1 * heapq.heappop(h)
		maxi = max(maxi, ans / float(s))
		if s in d:
			for i in d[s]:
				heapq.heappush(h, -1 * i)
	print(max(maxi, 0))


from sys import stdin, stdout
from collections import defaultdict
import heapq
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a1 = list(map(int, input().strip().split()))
	b1 = list(map(int, input().strip().split()))
	d = defaultdict(list)
	for i in range(n):
		key = b1[i]
		value = a1[i]
		d[key].append(-1 * value)
	li = d[0]
	heapq.heapify(li)
	maxi = 0
	k = []
	sumi = 0
	length = 0
	while True:
		if not li:
			break
		ele = -1 * heapq.heappop(li)
		k.append(ele)
		length += 1
		sumi += ele
		maxi = max(maxi, sumi / length)
		temp = d[length]
		for i in range(len(temp)):
			heapq.heappush(li, temp[i])
	print(maxi)


from queue import PriorityQueue
t = int(input())
for i in range(t):
	n = int(input())
	lsta = list(map(int, input().split()))
	lstb = list(map(int, input().split()))
	dic = {}
	for h in range(n):
		dic[h] = []
	for r in range(n):
		dic[lstb[r]].append(lsta[r])
	ind = 0
	su = 0
	a = 0
	q = PriorityQueue()
	c = 0
	lsta = []
	while True:
		if ind > n - 1:
			break
		else:
			for r in dic[ind]:
				q.put(-r)
			if q.empty() == True:
				ind = n + 1
			else:
				su += -q.get()
				ind += 1
				a += 1
				lsta.append(su / a)
	if lsta == []:
		print(0)
	else:
		print(max(0, max(lsta)))


import collections
from math import ceil, gcd, sqrt, log
from heapq import *
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	net = collections.defaultdict(list)
	maxHeap = []
	for (x, y) in zip(A, B):
		net[y].append(x)
	ans = 0
	s = 0
	tasksdone = 0
	for i in range(n):
		if i in net:
			l = net[i]
			for j in l:
				heappush(maxHeap, -j)
		if not maxHeap:
			break
		x = -heappop(maxHeap)
		s += x
		tasksdone += 1
		ans = max(ans, s / tasksdone)
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


from heapq import heapify, heappop, heappush

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	l = [[] for _ in range(n)]
	for (a, b) in zip(A, B):
		l[b].append(a)
	last = 0
	res = 0
	h = []
	for i in range(n):
		for a in l[i]:
			heappush(h, (-a, i))
		if not h:
			break
		assert len(h) > 0
		(a, b) = heappop(h)
		a = -a
		last += a
		res = max(res, last / (i + 1))
	print(res)
t = int(input())
for _ in range(t):
	solve()


from queue import PriorityQueue
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = [[] for i in range(n + 1)]
	dp = [0 for i in range(n + 1)]
	for i in range(n):
		ans[b[i]].append(l[i])
	lis = PriorityQueue()
	for i in range(1, n + 1):
		li = ans[i - 1]
		for x in li:
			lis.put(-x)
		if not lis.empty():
			dp[i] = dp[i - 1]
			dp[i] += -lis.get()
		else:
			break
	maxe = 0
	for i in range(1, n + 1):
		dp[i] /= i
		maxe = max(dp[i], maxe)
	maxe = max(dp)
	print('{:6f}'.format(maxe))


import collections, heapq
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	preq = collections.defaultdict(list)
	for i in range(n):
		preq[b[i]].append(a[i])
	heap = []
	for i in preq[0]:
		heapq.heappush(heap, -i)
	i = 1
	ans = 0
	sm = 0
	while heap:
		cand = -heapq.heappop(heap)
		sm += cand
		ans = max(ans, sm / i)
		for j in preq[i]:
			heapq.heappush(heap, -j)
		i += 1
	print('{:.6f}'.format(max(ans, 0)))


from sys import stdin, stdout
input = stdin.readline

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	g = [[] for i in range(n)]
	unused = SortedList([])
	for i in range(n):
		g[b[i]].append(a[i])
		if b[i] == 0:
			unused.add(a[i])
	curr_sum = 0
	curr_eles = 0
	maxi = 0
	while len(unused):
		x = unused.pop()
		curr_sum += x
		curr_eles += 1
		maxi = max(maxi, curr_sum / curr_eles)
		if curr_eles < n:
			for i in g[curr_eles]:
				unused.add(i)
	print(maxi)


from heapq import heappush, heappop
from sys import stdin
input = stdin.readline

class Plan:
	__slots__ = ['effectiveness', 'index']

	def __init__(self, effectiveness, index):
		self.effectiveness = effectiveness
		self.index = index

def solve(N, training):
	answer = 0
	count = 0
	training = sorted(training, key=lambda x: x.index)
	usable = []
	first = 0
	for k in range(1, N + 1):
		while first < N and training[first].index == k - 1:
			heappush(usable, -training[first].effectiveness)
			first += 1
		if not usable:
			break
		count += -heappop(usable)
		answer = max(answer, count / k)
	return answer
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	B = [int(x) for x in input().strip().split()]
	training = [Plan(a, b) for (a, b) in zip(A, B)]
	print('{0:.6f}'.format(solve(N, training)))


from heapq import heappush, heappop

def solve(n, arr):
	j = 0
	(a, b) = (0.0, 0.0)
	heap = []
	for i in range(n):
		while j < n and arr[j][1] <= i:
			heappush(heap, -arr[j][0])
			j += 1
		if not heap:
			break
		else:
			a -= heappop(heap)
			b = max(b, a / (i + 1))
	return b
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	arr = list(zip(a, b))
	arr.sort(key=lambda x: (x[1], -x[0]))
	if arr[0][1] > 0:
		print(0)
		continue
	print('%.7f' % solve(n, arr))


import heapq
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	req = list(map(int, input().split()))
	ans = 0
	dit = {}
	for i in range(n):
		if req[i] in dit:
			dit[req[i]].append(arr[i])
		else:
			dit[req[i]] = [arr[i]]
	hp = []
	i = 0
	count = 0
	s = 0
	while True:
		if i not in dit:
			if not hp:
				break
			else:
				s += -heapq.heappop(hp)
		else:
			m = max(dit[i])
			if not hp or (hp and -hp[0] < m):
				s += m
				dit[i].remove(m)
				for e in dit[i]:
					heapq.heappush(hp, -e)
			else:
				s += -heapq.heappop(hp)
				for e in dit[i]:
					heapq.heappush(hp, -e)
		count += 1
		curr = s / count
		ans = max(ans, curr)
		i += 1
	print('%.6f' % ans)


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	pairs = defaultdict(list)
	for i in range(N):
		pairs[B[i]].append(A[i])
	breakpoints = set()
	for k in pairs:
		breakpoints.add(k)
		pairs[k].sort()
	breakpoints = sorted(list(breakpoints))
	j = 0
	m = len(breakpoints)
	lst = pairs[0]
	ans = [0]
	s = 0
	for i in range(N):
		if j < m - 1 and i >= breakpoints[j + 1]:
			lst.extend(pairs[breakpoints[j + 1]])
			lst.sort()
			j += 1
		if not lst:
			break
		s += lst.pop()
		ans.append(s / (i + 1))
	print(max(ans))


import heapq
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	sb = [(b[i], i) for i in range(n)]
	sb.sort(reverse=True)
	hp = []
	summ = maxval = 0
	for k in range(n):
		while sb and sb[-1][0] <= k:
			idx = sb[-1][1]
			sb.pop()
			heapq.heappush(hp, -a[idx])
		if hp:
			ai = -heapq.heappop(hp)
			summ += ai
			if summ / (k + 1) > maxval:
				maxval = summ / (k + 1)
		else:
			break
	print(maxval)


N = 10
tree = [0] * (2 * N)

def build(arr):
	for i in range(n):
		tree[n + i] = arr[i]
	for i in range(n - 1, 0, -1):
		tree[i] = tree[i << 1] + tree[i << 1 | 1]

def updateTreeNode(p, value):
	tree[p + n] = value
	p = p + n
	i = p
	while i > 1:
		tree[i >> 1] = tree[i] + tree[i ^ 1]
		i >>= 1

def query(l, r):
	res = 0
	l += n
	r += n
	while l < r:
		if l & 1:
			res += tree[l]
			l += 1
		if r & 1:
			r -= 1
			res += tree[r]
		l >>= 1
		r >>= 1
	return res
from heapq import heappop, heappush, heapify
for i in range(int(input())):
	heap = []
	heapify(heap)
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([B[i], A[i]])
	l = sorted(l)
	j = 0
	cs = 0.0
	ms = 0.0
	for req in range(n):
		while j < n and l[j][0] <= req:
			heappush(heap, -l[j][1])
			j += 1
		if heap == []:
			break
		else:
			cs -= heappop(heap)
			ms = max(ms, cs / (req + 1))
	print('{0:.6f}'.format(ms))


from heapq import heappush, heappop
for tcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	la = [[] for i in range(n + 1)]
	for (i, k) in enumerate(b):
		la[k].append(-a[i])
	pq = []
	k = 0
	s = 0
	ans = 0.0
	while len(la[k]) > 0 or len(pq) > 0:
		while len(la[k]) > 0:
			heappush(pq, la[k].pop())
		s -= heappop(pq)
		k += 1
		ans = max(ans, s / k)
	print('{:.6f}'.format(ans))


from heapq import heappop, heappush, heapify
for i in range(int(input())):
	heap = []
	heapify(heap)
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([B[i], A[i]])
	l = sorted(l)
	j = 0
	cs = 0.0
	ms = 0.0
	for req in range(n):
		while j < n and l[j][0] <= req:
			heappush(heap, -l[j][1])
			j += 1
		if heap == []:
			break
		else:
			cs -= heappop(heap)
			ms = max(ms, cs / (req + 1))
	print('{0:.6f}'.format(ms))


import math
import itertools
import heapq
from math import floor, ceil

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def isSubsequence(s, t):
	for i in range(0, len(s)):
		try:
			index = t.index(s[i])
		except ValueError:
			return False
		t = t[index + 1:]
	return True
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	D = {}
	nums = set()
	for i in range(N):
		req = B[i]
		if req in D:
			D[req].append(A[i])
		else:
			D[req] = [A[i]]
		nums.add(B[i])
	nums = sorted(list(nums))
	soFar = 0
	ans = 0
	taken = 0
	h = []
	heapq.heapify(h)
	for req in range(max(nums) + 1):
		if taken < req:
			break
		else:
			if req in D:
				l = D[req][:]
				for x in range(len(l)):
					heapq.heappush(h, -l[x])
			if len(h) == 0:
				break
			currMax = -heapq.heappop(h)
			soFar += currMax
			taken += 1
			ans = max(ans, soFar / taken)
	while h:
		currMax = -heapq.heappop(h)
		soFar += currMax
		taken += 1
		ans = max(ans, soFar / taken)
	print(ans)


from collections import defaultdict
import heapq
t = int(input())
for _ in range(t):
	length = int(input())
	eff = list(map(int, input().split()))
	req = list(map(int, input().split()))
	dicti = defaultdict(list)
	for i in range(length):
		dicti[req[i]].append(eff[i])
	cand = []
	ans = []
	for i in range(length):
		for j in dicti[i]:
			heapq.heappush(cand, -j)
		if len(cand) == 0:
			break
		ans.append(heapq.heappop(cand))
	curr = 0
	for i in range(len(ans)):
		curr -= ans[i]
		ans[i] = curr / (i + 1)
	ans.append(0)
	print(max(ans))


from heapq import heappush, heapify, heappop
t = int(input())
for z in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		d[i] = []
	for i in range(n):
		if b[i] in d:
			d[b[i]].append(-a[i])
	max_ans = 0
	ans = 0
	count = 0
	fh = []
	lh = 0
	for i in range(n):
		for x in d[count]:
			heappush(fh, x)
			lh += 1
		if lh == 0:
			break
		x = heappop(fh)
		lh -= 1
		count += 1
		ans -= x
		max_ans = max(max_ans, ans / count)
	print(max_ans)


import heapq
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(n):
		c.append([b[i], a[i]])
	c.sort(key=lambda x: (x[0], -x[1]))
	ans = [0]
	h = []
	x = 0
	i = 0
	while i < n:
		if c[i][0] <= x:
			if x == 0:
				ans.append(c[i][1])
				i += 1
			else:
				while i < n and c[i][0] <= x:
					heapq.heappush(h, c[i][1] * -1)
					i += 1
				ans.append((ans[-1] * x + heapq.heappop(h) * -1) / (x + 1))
			x += 1
		elif c[i][0] > x:
			if len(h) == 0:
				break
			ans.append((ans[-1] * x + heapq.heappop(h) * -1) / (x + 1))
			x += 1
	if x < n - 1:
		while x < n - 1:
			if len(h) == 0:
				break
			ans.append((ans[-1] * x + heapq.heappop(h) * -1) / (x + 1))
			x += 1
	print('{0:.6f}'.format(max(ans)))


from heapq import heappop, heappush, heapify
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	ll = [[] for i in range(n)]
	heapify(l)
	for i in range(n):
		if b[i] == 0:
			heappush(l, -1 * a[i])
		ll[b[i]].append(a[i])
	ans = 0
	count = 0
	anss = 0
	while len(l):
		if count == 0:
			ans = -l[0]
			heappop(l)
			count += 1
			if count <= n - 1:
				for i in range(len(ll[count])):
					heappush(l, -1 * ll[count][i])
		else:
			ans += -l[0]
			heappop(l)
			count += 1
			if count <= n - 1:
				for i in range(len(ll[count])):
					heappush(l, -1 * ll[count][i])
		anss = max(anss, ans / count)
	print(anss)


import heapq
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	l = []
	for i in range(0, n):
		l.append([])
	for i in range(0, n):
		l[b[i]].append(-a[i])
	ans = []
	if l[0] == []:
		print(0)
		continue
	heapq.heapify(l[0])
	ans.append(heapq.heappop(l[0]))
	for i in range(1, n):
		for j in l[i]:
			heapq.heappush(l[0], j)
		if len(l[0]) == 0:
			break
		ans.append(ans[-1] + heapq.heappop(l[0]))
	if ans == []:
		print(0)
		continue
	for i in range(0, len(ans)):
		ans[i] = ans[i] / (i + 1)
	print(max(0, -min(ans)))


import math, bisect, heapq, random, sys, itertools
input = sys.stdin.readline

def gprint(t, ans):
	print(f'Case #{t + 1}:', ans)
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
ANS = []
for t in range(int(input())):
	n = int(input())
	a = ints()
	b = ints()
	arr = []
	bad = []
	(n1, n2) = (0, 0)
	for i in range(n):
		if a[i] >= 0:
			arr.append((b[i], a[i]))
			n1 += 1
		else:
			bad.append((b[i], a[i]))
			n2 += 1
	arr.sort()
	bad.sort()
	ans = 0
	s = 0
	(i1, i2) = (0, 0)
	c = 0
	pos = []
	neg = []
	while True:
		while i1 < n1:
			if arr[i1][0] <= c:
				bisect.insort(pos, arr[i1][1])
				i1 += 1
			else:
				break
		if pos:
			s += pos.pop()
			c += 1
			ans = max(ans, s / c)
			continue
		while i2 < n2:
			if bad[i2][0] <= c:
				bisect.insort(neg, bad[i2][1])
				i2 += 1
			else:
				break
		if neg:
			s += neg.pop()
			c += 1
		else:
			break
	print(ans)