文理学院程序设计在线练习


猴子卖桃

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 42   Accepted Submission(s): 18
Problem Description

花果山今年桃子大丰收,不光是数量多,种类也不少,什么蟠桃、蜜桃、油桃、黄桃......,应有尽有。猴子们觉得光靠自己吃是吃不完的,于是就打算将多余的桃子进行销售,为此它们特意建了一家桃子专卖店。

由于商店面积不够大,无法同时摆放所有的桃子;另外,桃子销售猴员没有经过专门的训练,若在专卖店里同时摆放不同类别的桃子,它们也会搞不清楚。所以,只能是一天摆放和销售某一个品种的桃子。当然由于桃子价格公道且质量又好,所以,当天上柜销售的桃子不管数量如何总是能够销售一空的。

需要补充一点,桃子是有保质期的,若超过了保质期就不能销售了。

现在的任务是:假设已经知道了用于销售的桃子的种类、每种的数量以及每种桃子的保质期,请你计算一下,若能合理安排销售顺序,最多能卖出去多少个桃子?

说明,这里的保质期指的是从开始营业的那一天起,可以保存的天数。

例如:有3种桃子A,B,C,数量分别为5,5,10,保质期分别是2,1,1。我们可以有以下几种可能的安排。
安排一:第1天卖品种A,这种情况下第2天只能停业。总计销售5。
安排二:第1天卖品种B,第2天卖品种A。总计销售10。
安排三:第1天卖品种C,第2天卖品种A。总计销售15。
于是,我们得到的结论是最多能够销售15个桃子。

Input

输入数据的第一行为一个正整数T(0<T<=20),表示测试数据的组数,然后是T组测试数据。
对于每组测试,首先是一个整数n(0 < n <= 10000),表示桃子的种类,后面接2行数据。
前面一行的n个整数,分别表示可用于销售的这n种桃子的数量bi(0 <= bi <= 10000),数据之间用空格分开。
后面一行的n个整数,分别表示这n种桃子的保质期ci(0 <= ci <= 10000),数据之间用空格分开。

Output

对于每组测试,输出最多能够销售的桃子总数。

Sample Input
2
3
5 5 10
2 1 1
5
12 2 10 8 15
2 2 1 8 8
Sample Output
15
45
Hint

第二组测试中有5种桃子A,B,C,D,E,数量分别为12,2,10,8,15,保质期分别是2,2,1,8,8。一种合理的安排是:
第一天卖品种C(10个),第二天卖品种A(12个),第3天卖品种D(8个),第4天卖品种E(15个),总计销售45个。

Source

2012校计算机技能竞赛