1994 - 捕杀恶龙!

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

 动物园有一条n个头的恶龙,你希望雇佣一些骑士把它杀死(也就是砍掉所有的头)。现在有m个骑士可以雇佣,一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头,且需要支付 x 个金币。如何雇佣骑士才能砍掉恶龙所有的头,并且支付最小的金币?(注意:一个骑士只能砍一个头并且仅能被雇佣1次。)

题目输入

输入多组数据,第一行二个整数n、m,(1<=n,m<=20000);以下n行每行为一个整数,即恶龙每个头的直径,以下m行为一个整数,即每个骑士的能力。输入结束标志为n=m=0.

题目输出

对于每组数据,输出最少花费。如果无解,输出:“Loowater is doomed!”

提示:因为要保证用的钱最少,所以先把骑士按照能力值从小到大进行排序。然后从最小的开始一个一个进行匹配。

输入/输出样例

输入格式

2 3
5
4
7
8
4
2 1
5
5
10
0 0

输出格式

11
Loowater is doomed!