Nick has n bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda a_{i} and bottle volume b_{i} (a_{i} ≤ b_{i}).

Nick has decided to pour all remaining soda into minimal number of bottles, moreover he has to do it as soon as possible. Nick spends x seconds to pour x units of soda from one bottle to another.

Nick asks you to help him to determine k — the minimal number of bottles to store all remaining soda and t — the minimal time to pour soda into k bottles. A bottle can't store more soda than its volume. All remaining soda should be saved.


-----Input-----

The first line contains positive integer n (1 ≤ n ≤ 100) — the number of bottles.

The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100), where a_{i} is the amount of soda remaining in the i-th bottle.

The third line contains n positive integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 100), where b_{i} is the volume of the i-th bottle.

It is guaranteed that a_{i} ≤ b_{i} for any i.


-----Output-----

The only line should contain two integers k and t, where k is the minimal number of bottles that can store all the soda and t is the minimal time to pour the soda into k bottles.


-----Examples-----
Input
4
3 3 4 3
4 7 6 5

Output
2 6

Input
2
1 1
100 100

Output
1 1

Input
5
10 30 5 6 24
10 41 7 8 24

Output
3 11



-----Note-----

In the first example Nick can pour soda from the first bottle to the second bottle. It will take 3 seconds. After it the second bottle will contain 3 + 3 = 6 units of soda. Then he can pour soda from the fourth bottle to the second bottle and to the third bottle: one unit to the second and two units to the third. It will take 1 + 2 = 3 seconds. So, all the soda will be in two bottles and he will spend 3 + 3 = 6 seconds to do it.

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

Starter code:

Solutions:
f = lambda : list(map(int, input().split()))
n = int(input())
(a, b) = (f(), f())
d = [[None] * 10001 for i in range(n)]

def g(i, s):
	if s <= 0:
		return (0, s)
	if i == n:
		return (10000000.0, 0)
	if not d[i][s]:
		(x, y) = g(i + 1, s - b[i])
		d[i][s] = min(g(i + 1, s), (x + 1, y + b[i] - a[i]))
	return d[i][s]
(x, y) = g(0, sum(a))
print(x, y)


n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
minTime = [[{} for j in range(101)] for k in range(101)]
minTime[1][1][b[0] - a[0]] = 0
minTime[1][0][-a[0]] = a[0]
validVolumes = {-a[0], b[0] - a[0]}
for bottle in range(1, n):
	validVolumesNew = set()
	for bottlesUsed in range(0, bottle + 1):
		for volumeLeft in validVolumes:
			if volumeLeft in minTime[bottle][bottlesUsed]:
				currTime = minTime[bottle][bottlesUsed][volumeLeft]
				pouredTime = currTime + a[bottle]
				includedTime = currTime
				if volumeLeft - a[bottle] not in minTime[bottle + 1][bottlesUsed]:
					minTime[bottle + 1][bottlesUsed][volumeLeft - a[bottle]] = 100000000
				minTime[bottle + 1][bottlesUsed][volumeLeft - a[bottle]] = min(minTime[bottle + 1][bottlesUsed][volumeLeft - a[bottle]], pouredTime)
				if volumeLeft + b[bottle] - a[bottle] not in minTime[bottle + 1][bottlesUsed + 1]:
					minTime[bottle + 1][bottlesUsed + 1][volumeLeft + b[bottle] - a[bottle]] = 100000000
				minTime[bottle + 1][bottlesUsed + 1][volumeLeft + b[bottle] - a[bottle]] = min(minTime[bottle + 1][bottlesUsed + 1][volumeLeft + b[bottle] - a[bottle]], includedTime)
				validVolumesNew.add(volumeLeft - a[bottle])
				validVolumesNew.add(volumeLeft + b[bottle] - a[bottle])
	validVolumes = validVolumesNew
	validVolumesNew = set()
exitFlag = False
lowestTime = 1000000000
for bottlesUsed in range(0, n + 1):
	for volumeLeft in range(0, n * 101):
		if volumeLeft in minTime[n][bottlesUsed]:
			exitFlag = True
			lowestTime = min(lowestTime, minTime[n][bottlesUsed][volumeLeft])
	if exitFlag:
		print(bottlesUsed, lowestTime)
		exit()


import sys
input = sys.stdin.buffer.readline
n = int(input())
soda = list(map(int, input().split()))
volume = list(map(int, input().split()))
dp = [[{} for j in range(n + 1)] for k in range(n + 1)]
dp[0][1][volume[0] - soda[0]] = 0
total = soda[0]
for i in range(0, n - 1):
	total += soda[i + 1]
	dp[i + 1][1][volume[i + 1] - total] = total - soda[i + 1]
	for bottle in range(1, i + 2):
		for volume_left in dp[i][bottle]:
			if volume_left - soda[i + 1] not in dp[i + 1][bottle]:
				dp[i + 1][bottle][volume_left - soda[i + 1]] = dp[i][bottle][volume_left] + soda[i + 1]
			dp[i + 1][bottle][volume_left - soda[i + 1]] = min(dp[i][bottle][volume_left] + soda[i + 1], dp[i + 1][bottle][volume_left - soda[i + 1]])
			if volume_left + volume[i + 1] - soda[i + 1] not in dp[i + 1][bottle + 1]:
				dp[i + 1][bottle + 1][volume_left + volume[i + 1] - soda[i + 1]] = dp[i][bottle][volume_left]
			dp[i + 1][bottle + 1][volume_left + volume[i + 1] - soda[i + 1]] = min(dp[i][bottle][volume_left], dp[i + 1][bottle + 1][volume_left + volume[i + 1] - soda[i + 1]])
flag = 0
mini = 99999999999
i = 0
for i in range(1, n + 1):
	for j in dp[n - 1][i]:
		if j >= 0:
			mini = min(mini, dp[n - 1][i][j])
			flag = 1
	if flag == 1:
		break
print(i, mini)


import math
from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
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')
sys.setrecursionlimit(10 ** 5)

def calc(i, total):
	if total <= 0:
		return [0, total]
	if i == -1:
		return [float('inf'), float('inf')]
	if dp[i, total][0] != -1:
		return dp[i, total]
	poss1 = calc(i - 1, total)
	poss2 = calc(i - 1, total - b[i])
	poss2[0] += 1
	poss2[1] += b[i] - a[i]
	if poss1[0] < poss2[0]:
		dp[i, total][0] = poss1[0]
		dp[i, total][1] = poss1[1]
	elif poss1[0] > poss2[0]:
		dp[i, total][0] = poss2[0]
		dp[i, total][1] = poss2[1]
	elif poss1[1] < poss2[1]:
		dp[i, total][0] = poss1[0]
		dp[i, total][1] = poss1[1]
	else:
		dp[i, total][0] = poss2[0]
		dp[i, total][1] = poss2[1]
	return [dp[i, total][0], dp[i, total][1]]
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = sum(a)
dp = defaultdict(lambda : [-1, 0])
val = calc(n - 1, s)
print(val[0], val[1])