摇钱树

题目描述

Cpg 正在游览一个梦中之城,在这个城市中有 $n$ 棵摇钱树。这下,可让 Cpg 看傻了。可是 Cpg 只能在这个城市中呆 $k$ 天,但是现在摇钱树已经成熟了,每天每棵都会掉下不同的金币(不属于 Cpg!)。Cpg 每天可以砍掉其中一颗,并获得其树上所有的金币(怎么会有这种好事)。请你帮助 Cpg 算出他在这 $k$ 天中最多能获得多少金币。

输入输出格式

输入格式


**本题单测试点内有多组数据**。 每个测试点中有不超过 $10$ 组的测试数据。 每组测试数据: 第一行两个整数 $n,k$。 第二行包含 $n$ 个整数 $m_i$,表示 Cpg 刚看到这 $n$ 棵树时每刻树上的金币数。 第三行 $n$ 个整数 $b_i$,表示每颗摇钱树,每天将会掉落的金币。 以 `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 \le n, k \le 10^3$,$1 \le m_i \le 10^5$,$1 \le b_i \le 10^3$。