A21025.摇钱树
提高+/省选-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
Cpg 正在游览一个梦中之城,在这个城市中有 n 棵摇钱树。这下,可让 Cpg 看傻了。可是 Cpg 只能在这个城市中呆 k 天,但是现在摇钱树已经成熟了,每天每棵都会掉下不同的金币(不属于 Cpg!)。Cpg 每天可以砍掉其中一颗,并获得其树上所有的金币(怎么会有这种好事)。请你帮助 Cpg 算出他在这 k 天中最多能获得多少金币。
输入格式
本题单测试点内有多组数据。
每个测试点中有不超过 10 组的测试数据。
每组测试数据:
第一行两个整数 n,k。
第二行包含 n 个整数 mi,表示 Cpg 刚看到这 n 棵树时每刻树上的金币数。
第三行 n 个整数 bi,表示每颗摇钱树,每天将会掉落的金币。
以 0 0
结束。
输出格式
对每组测试数据,输出仅一行,Cpg 在 k 天中能获得的最大金币数。
输入输出样例
输入#1
3 3 10 20 30 4 5 6 4 3 20 30 40 50 2 7 6 5 0 0
输出#1
47 104
说明/提示
数据范围与约定
- 对于 100% 的数据,1≤n,k≤103,1≤mi≤105,1≤bi≤103。