#z1045. 水瓶

水瓶

水瓶

【问题描述】

小A有很多瓶没有喝完的水,为了节约空间,现在他想把剩余的水集中起来。

具体来说,第 ii 瓶水有剩余水量 aia_i 和最大容积 bib_i,在不超过瓶子容积的前提下,小A可以把任意多的水从一个瓶子倒向另一个瓶子,所花费的时间等同于倒过去的水的体积。

现在小A想要知道,他最多能得到多少个空瓶,以及在得到最多的空瓶的前提下,他最少需要花费的时间。

【输入格式】

第一行一个正整数 nn,表示瓶子数量。

第二行 nn 个正整数 aia_i,表示每个瓶子的剩余水量。

第三行 nn 个正整数 bib_i,表示每个瓶子的最大容积,保证 ai<=bia_i<=b_i

【输出格式】

一行两个整数,第一个是最多的空瓶数,第二个是在得到最多空瓶数的前提下所需的最少时间。

【输入样例】

4 3 3 4 3 4 7 6 5

【输出样例】

2 6

【样例解释】

把第一个瓶子里的 33 个单位的水全部倒入第二个瓶子,把第四个瓶子里的水倒 11 个单位到第二个瓶子,22 个单位到第三个瓶子。

【数据规模和约定】

对于 70% 的数据,保证 1<=n,ai,bi<=1001<=n, a_i, b_i <=100

对于100%的数据,保证 1<=n,ai,bi<=5001<= n, a_i, b_i <=500