← 返回题目列表

Codeforces · 730/J

J. 瓶子

中文机器翻译题面 查看原题

尼克在生日后还剩下 n 瓶苏打水。每个瓶子由两个值描述:苏打水剩余量 ai 和瓶子体积 bi (ai ≤ bi)。

尼克决定将所有剩余的苏打水倒入最少数量的瓶子中,而且他必须尽快完成。尼克花了 x 秒将 x 单位的苏打水从一个瓶子倒到另一个瓶子里。

尼克要求你帮助他确定 k(存放所有剩余苏打水的最少瓶子数量)和 t(将苏打水倒入 k 个瓶子的最短时间)。一瓶苏打水的容量不能超过其容量。所有剩余的苏打水都应该保存起来。

输入

第一行包含正整数 n (1 ≤ n ≤ 100) — 瓶子数量。

第二行包含 n 个正整数 a1, a2, ..., an (1 ≤ ai ≤ 100),其中 ai 是第 i 个瓶子中剩余的苏打水量。

第三行包含n个正整数b1, b2, ..., bn (1 ≤ bi ≤ 100),其中bi是第i个瓶子的体积。

对于任何 i,保证 ai ≤ bi。

输出

唯一的一行应包含两个整数 k 和 t,其中 k 是可以存储所有苏打水的最小瓶子数量,t 是将苏打水倒入 k 个瓶子的最短时间。

示例

输入 #1

4
3 3 4 3
4 7 6 5

输出 #1

2 6

输入 #2

2
1 1
100 100

输出 #2

1 1

输入 #3

5
10 30 5 6 24
10 41 7 8 24

输出 #3

3 11

注意

在第一个示例中,Nick 可以将苏打水从第一个瓶子倒入第二个瓶子。需要 3 秒钟。之后第二瓶将包含 3 + 3 = 6 单位的苏打水。然后他可以将苏打水从第四个瓶子倒到第二个瓶子和第三个瓶子:一个单位到第二个瓶子,两个单位到第三个瓶子。需要 1 + 2 = 3 秒。因此,所有苏打水都装在两瓶中,他将花费 3 + 3 = 6 秒来完成。