Problem2780--勇者斗恶龙[The Dragon of Loowater,UVa11292]

2780: 勇者斗恶龙[The Dragon of Loowater,UVa11292]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

很久很久以前,在Loowater王国有一条N个头的恶龙,国王命令骑士们把他杀死(即砍掉所有头)。王国里有M个骑士可以雇佣,一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头,且需要支付x个金币。
如何雇佣骑士才能砍掉恶龙的所有头,且需要支付的金币最少?注意,一个骑士只能砍一个头(且不能被雇佣两次)

Input

输入有多组数据。
每组数据第一行是空格隔开的正整数N和M,分别表示恶龙的头数N和骑士的数量M。
接下来N行,每行一个整数,表示恶龙的每个头的直径;
接下来M行,每行一个整数,表示每个骑士的能力值。当有单独的一行“0 0”时,表示输入结束。(1≤N,M≤20000)

Output

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

Sample Input Copy

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

Sample Output Copy

11
Loowater is doomed!

Source/Category