There are n glasses on the table numbered 1, …, n. The glass i can hold up to a_i units of water, and currently contains b_i units of water.

You would like to choose k glasses and collect as much water in them as possible. To that effect you can pour water from one glass to another as many times as you like. However, because of the glasses' awkward shape (and totally unrelated to your natural clumsiness), each time you try to transfer any amount of water, half of the amount is spilled on the floor.

Formally, suppose a glass i currently contains c_i units of water, and a glass j contains c_j units of water. Suppose you try to transfer x units from glass i to glass j (naturally, x can not exceed c_i). Then, x / 2 units is spilled on the floor. After the transfer is done, the glass i will contain c_i - x units, and the glass j will contain min(a_j, c_j + x / 2) units (excess water that doesn't fit in the glass is also spilled).

Each time you transfer water, you can arbitrarlly choose from which glass i to which glass j to pour, and also the amount x transferred can be any positive real number.

For each k = 1, …, n, determine the largest possible total amount of water that can be collected in arbitrarily chosen k glasses after transferring water between glasses zero or more times.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of glasses.

The following n lines describe the glasses. The i-th of these lines contains two integers a_i and b_i (0 ≤ b_i ≤ a_i ≤ 100, a_i > 0) — capacity, and water amount currently contained for the glass i, respectively.

Output

Print n real numbers — the largest amount of water that can be collected in 1, …, n glasses respectively. Your answer will be accepted if each number is within 10^{-9} absolute or relative tolerance of the precise answer.

Example

Input


3
6 5
6 5
10 2


Output


7.0000000000 11.0000000000 12.0000000000

Note

In the sample case, you can act as follows:

  * for k = 1, transfer water from the first two glasses to the third one, spilling (5 + 5) / 2 = 5 units and securing 2 + (5 + 5) / 2 = 7 units;
  * for k = 2, transfer water from the third glass to any of the first two, spilling 2 / 2 = 1 unit and securing 5 + 5 + 2 / 2 = 11 units;
  * for k = 3, do nothing. All 5 + 5 + 2 = 12 units are secured.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
n = int(input())
dp = [[-10 ** 8] * 10002 for _ in range(n + 1)]
dp[0][0] = 0
total = 0
for i in range(n):
	(a, b) = map(int, input().split())
	total += b
	for k in range(n - 1, -1, -1):
		for c in range(10001 - a, -1, -1):
			dp[k + 1][c + a] = max(dp[k + 1][c + a], dp[k][c] + b)
ans = [0 for i in range(n + 1)]
for j in range(1, n + 1):
	maxi = 0
	for i in range(10002):
		con = dp[j][i]
		maxi = max(maxi, min(i, (con + total) / 2))
	ans[j] = maxi
for i in range(1, n + 1):
	print(ans[i], end=' ')


from sys import stdin, stdout
from bisect import bisect_left, bisect_right

def main():
	n = int(stdin.readline())
	g = [(0, 0)]
	need = [(0, 0)]
	for _ in range(n):
		g.append(list(map(int, stdin.readline().split())))
		need.append(g[-1][0] - g[-1][1])
	sm = sum([i[1] for i in g])
	dp = [[-1 for _ in range(sm + 1)] for _ in range(n + 1)]
	for i in range(n, 0, -1):
		dp[i][sm] = 0
	ans = []
	for i in range(n):
		mx = -1
		temp_dp = [[-1 for _ in range(sm + 1)] for kx in range(n + 1 - i)]
		for j in range(n - i, 0, -1):
			mxs = -1
			for (k, v) in enumerate(dp[j]):
				if v != -1:
					fillable = min(need[j], (k - g[j][1]) / 2)
					pos = k - int(fillable * 2) - g[j][1]
					temp_dp[j - 1][pos] = max(temp_dp[j - 1][pos], v + g[j][1] + fillable)
					temp_dp[j][k] = max(temp_dp[j][k], v)
					dp[j - 1][k] = max(dp[j - 1][k], v)
					mx = max(mx, temp_dp[j - 1][pos], temp_dp[j][k])
		dp = temp_dp
		ans.append(str(mx))
	print(' '.join(ans))
main()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
import time
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
start_time = time.time()

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 998244353

def solve():
	N = getInt()
	dp = [[-10 ** 18 for j in range(10002)] for i in range(N + 1)]
	dp[0][0] = 0
	glasses = getMat(N)
	TV = sum([b for (a, b) in glasses])
	for i in range(N):
		(a, b) = glasses[i]
		for j in range(i, -1, -1):
			for k in range(100 * j, -1, -1):
				if dp[j][k] > -10 ** 18:
					dp[j + 1][k + a] = max(dp[j][k] + b, dp[j + 1][k + a])
	ans = []
	for i in range(1, N + 1):
		tmp = 0
		for j in range(100 * i + 1):
			tmp = max(tmp, min(j, (dp[i][j] + TV) / 2))
		ans.append(tmp)
	print(*ans)
	return
solve()


n = int(input())
k = []
dics = []
for _ in range(n):
	(a, b) = map(int, input().split())
	k.append([a, b])
	dics.append({})
sums = 0
for i in range(n):
	sums += k[i][1]
for i in range(n):
	r1 = k[i][0]
	r2 = k[i][1]
	for j in range(n - 1, -1, -1):
		for t in dics[j]:
			if t + r1 in dics[j + 1]:
				dics[j + 1][t + r1] = max(dics[j + 1][t + r1], dics[j][t] + r2)
			else:
				dics[j + 1][t + r1] = dics[j][t] + r2
	if r1 in dics[0]:
		dics[0][r1] = max(dics[0][r1], r2)
	else:
		dics[0][r1] = r2
ans = []
for i in range(n):
	tmp = 0
	for j in dics[i]:
		tmp = max(min((sums + dics[i][j]) / 2, j), tmp)
	ans.append(str(tmp))
print(' '.join(ans))


import os
import sys
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))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
n = N()
p = [tuple(RL()) for _ in range(n)]
p.sort(key=lambda x: x[0])
S = sum((v[1] for v in p))
dic = [[-1] * 10001 for _ in range(n + 1)]
dic[0][0] = 0
(l, r) = ([0], [0])
for i in range(n):
	(dc, dv) = p[i]
	for k in range(i, -1, -1):
		t = -1
		for c in range(r[k], l[k] - 1, -1):
			if dic[k][c] == -1:
				continue
			if dic[k][c] <= t:
				dic[k][c] = -1
			else:
				t = dic[k][c]
				if dic[k][c] + dv > dic[k + 1][c + dc]:
					dic[k + 1][c + dc] = dic[k][c] + dv
		r[k] += dc - p[i - k][0]
	l.append(l[-1] + dc)
	r.append(l[-1])
print(*[max((min(c, (dic[k][c] + S) / 2) for c in range(l[-1] + 1) if dic[k][c] > -1)) for k in range(1, n + 1)])


mod = 1000000007
eps = 10 ** (-9)
inf = 1000000000.0

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	A = []
	B = []
	for _ in range(N):
		(a, b) = map(int, input().split())
		A.append(a)
		B.append(b)
	vmax = sum(A)
	dp = [[-inf] * (vmax + 1)]
	dp[0][0] = 0.0
	for i in range(N):
		a = A[i]
		b = B[i]
		dp_new = [[-inf] * (vmax + 1) for _ in range(i + 2)]
		for j in range(i + 1):
			for v in range(vmax + 1):
				dp_new[j][v] = max(dp_new[j][v], dp[j][v] + b / 2)
				if v + a <= vmax:
					dp_new[j + 1][v + a] = max(dp_new[j + 1][v + a], dp[j][v] + b)
		dp = dp_new
	ans = [-1] * (N + 1)
	for k in range(1, N + 1):
		for v in range(vmax + 1):
			ans[k] = max(ans[k], min(dp[k][v], v))
	print(*ans[1:])
main()


n = int(input())
inf = 10 ** 8
dp = []
for k in range(n + 1):
	dp.append([-inf] * 10005)
dp[0][0] = 0
w = 0
for _ in range(k):
	(a, b) = map(int, input().split())
	w += b
	for k in range(n - 1, -1, -1):
		for i in range(10005 - a):
			dp[k + 1][i + a] = max(dp[k + 1][i + a], dp[k][i] + b)
out = []
for line in dp[1:]:
	poss = []
	for i in range(10005):
		cap = i
		con = line[i]
		poss.append(min(cap, (con + w) / 2))
	out.append(max(poss))
print(' '.join(map(str, out)))


def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = []
b = []
for _ in range(n):
	(aa, bb) = [int(x) for x in input().split()]
	a.append(aa)
	b.append(bb)
total = sum(b)
MAXCAP = sum(a)
dp = [[-float('inf') for _ in range(MAXCAP + 1)] for __ in range(n + 1)]
for glass in range(n):
	dp[0][0] = 0
for glass in range(n):
	for nGlassesTaken in range(glass + 1, 0, -1):
		for cap in range(MAXCAP, 0, -1):
			if cap - a[glass] >= 0:
				takeGlass = dp[nGlassesTaken - 1][cap - a[glass]] + b[glass]
				dp[nGlassesTaken][cap] = max(dp[nGlassesTaken][cap], takeGlass)
ans = [0 for _ in range(n + 1)]
for nGlassesTaken in range(1, n + 1):
	for cap in range(MAXCAP + 1):
		amount = dp[nGlassesTaken][cap]
		if amount != -float('inf'):
			amount2 = (total - amount) / 2.0
			amount3 = min(cap, amount + amount2)
			ans[nGlassesTaken] = max(ans[nGlassesTaken], amount3)
oneLineArrayPrint(ans[1:])


n = int(input())
p = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: (x[0], -x[1]))
dic = [[-1] * 10001 for _ in range(n + 1)]
dic[0][0] = 0
(l, r, s) = ([0], [0], 0)
for i in range(n):
	(dc, dv) = p[i]
	s += dv
	for k in range(i, -1, -1):
		m = -1
		for c in range(r[k], l[k] - 1, -1):
			if dic[k][c] == -1:
				continue
			if dic[k][c] <= m:
				dic[k][c] = -1
			else:
				m = dic[k][c]
				if dic[k][c] + dv > dic[k + 1][c + dc]:
					dic[k + 1][c + dc] = dic[k][c] + dv
		r[k] += dc - p[i - k][0]
	l.append(l[-1] + dc)
	r.append(l[-1])
print(*[max((min(c, (dic[k][c] + s) / 2) for c in range(l[k], r[k] + 1) if dic[k][c] > -1)) for k in range(1, n + 1)])


import os, sys
from io import BytesIO, IOBase
from math import inf

def main():
	n = int(input())
	(cap, su, su1) = ([], 0, 0)
	for _ in range(n):
		(a, b) = map(int, input().split())
		cap.append((a, b))
		su += b
		su1 += a
	dp = [[-inf] * (su1 + 1) for _ in range(n)]
	for i in cap:
		for j in range(n - 2, -1, -1):
			for k in range(1, su1 + 1 - i[0]):
				dp[j + 1][k + i[0]] = max(dp[j + 1][k + i[0]], dp[j][k] + i[1] / 2)
		dp[0][i[0]] = max(dp[0][i[0]], i[1] / 2)
	x = su / 2
	for i in range(n):
		val = 0
		for j in range(1, su1 + 1):
			val = max(val, min(j, x + dp[i][j]))
		print(val, end=' ')
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))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import io
import os
from collections import Counter, defaultdict, deque

def solve1(N, AB):
	ans = [0.0] * (N + 1)
	total = sum((b for (a, b) in AB))
	possible = set([(0, 0, 0)])
	for (a, b) in AB:
		for (take, cap, count) in list(possible):
			possible.add((take + b, cap + a, count + 1))
	for (take, cap, count) in possible:
		extra = (total - take) / 2
		remainingCap = cap - take
		temp = take + min(extra, remainingCap)
		temp2 = take + min((total - take) / 2, cap - take)
		temp3 = min((total + take) / 2, cap)
		temp4 = min(total + take, cap * 2) / 2.0
		assert temp == temp2 == temp3 == temp4
		ans[count] = max(ans[count], temp)
	return ' '.join((str(float(ans[i + 1])) for i in range(N)))

def solve(N, AB):
	ans = [0.0] * (N + 1)
	total = sum((b for (a, b) in AB))
	possible = defaultdict(int)
	possible[0, 0] = 0
	for (a, b) in AB:
		for ((cap, count), take) in list(possible.items()):
			possible[cap + a, count + 1] = max(possible[cap + a, count + 1], take + b)
	for ((cap, count), take) in possible.items():
		extra = (total - take) / 2
		remainingCap = cap - take
		temp = take + min(extra, remainingCap)
		ans[count] = max(ans[count], temp)
	return ' '.join((str(float(ans[i + 1])) for i in range(N)))
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(10000):
		N = random.randint(1, 10)
		AB = [sorted((random.randint(1, 10), random.randint(1, 10)), reverse=True) for i in range(N)]
		print('tc', _, N, AB)
		ans = solve(N, AB)
		ans1 = solve1(N, AB)
		print(ans)
		print(ans1)
		assert ans == ans1
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	AB = [tuple((int(x) for x in input().split())) for i in range(N)]
	ans = solve(N, AB)
	print(ans)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
AB = [tuple(map(int, input().split())) for i in range(n)]
SUMB = 0
for (a, b) in AB:
	SUMB += b

def calc(suma, sumb):
	return min(suma, (SUMB + sumb) / 2)
DP = [[-1] * 10005 for i in range(n + 1)]
DP[0][0] = 0
for i in range(n):
	(a, b) = AB[i]
	for j in range(i, -1, -1):
		for k in range(100 * j, -1, -1):
			if DP[j][k] != -1:
				DP[j + 1][k + a] = max(DP[j + 1][k + a], DP[j][k] + b)
A = []
for i in range(1, n + 1):
	ANS = 0
	for j in range(100 * i + 1):
		if DP[i][j] == -1:
			continue
		ANS = max(ANS, calc(j, DP[i][j]))
	A.append(ANS)
print(*A)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 10 ** 9 + 7
n = II()
ab = LLI(n)
s = sum((b for (a, b) in ab))

def chmax(i, j, val):
	if val > dp[i][j]:
		dp[i][j] = val
dp = [[-1] * 10005 for _ in range(n + 1)]
dp[0][0] = 0
cmx = 0
for (i, (a, b)) in enumerate(ab):
	for k in range(i, -1, -1):
		nc = cmx
		for c in range(cmx, -1, -1):
			pre = dp[k][c]
			if pre == -1:
				continue
			chmax(k + 1, c + a, pre + b)
			if c + a > nc:
				nc = c + a
		cmx = nc
aa = []
for k in range(1, n + 1):
	ans = 0
	for c in range(10005):
		v = dp[k][c]
		if v == -1:
			continue
		cur = min(c, v + (s - v) / 2)
		if cur > ans:
			ans = cur
	aa.append(ans)
print(*aa)


from sys import stdin, stdout

def glass_half_spilled(n, ab_a, a_a, sa, sb):
	dp = [[-1 for _ in range(sa + 1)] for _ in range(n + 1)]
	dp[0][0] = 0
	for i in range(1, n + 1):
		for k in range(i, 0, -1):
			for A in range(a_a[i], -1, -1):
				if dp[k - 1][A - ab_a[i - 1][0]] == -1:
					continue
				dp[k][A] = max(dp[k][A], dp[k - 1][A - ab_a[i - 1][0]] + ab_a[i - 1][1])
	r_a = []
	for k in range(1, n + 1):
		r = 0
		for A in range(sa, -1, -1):
			if dp[k][A] == -1:
				continue
			r = max(r, min(dp[k][A] / 2 + sb / 2, A))
		r_a.append(r)
	return r_a
n = int(stdin.readline())
ab_a = []
a_a = [0]
sb = 0
for _ in range(n):
	(a, b) = map(int, stdin.readline().split())
	ab_a.append([a, b])
	a_a.append(a + a_a[-1])
	sb += b
r_a = glass_half_spilled(n, ab_a, a_a, a_a[-1], sb)
stdout.write(' '.join(map(str, r_a)))