问题 4326 --5. 星球大战

4326: 5. 星球大战

题目描述

      兰姐姐是来自火星的女王。
    找到了失散多年的姐姐Horse countryxing,兰姐姐非常的兴奋。但是姐姐接下来告诉兰姐姐一个不幸的消息:塔图因星球上的沙兵,持着他们的枪,率领着克隆人部队,想要侵犯火星。
    兰姐姐感到非常害怕,因为她去地球玩了很多天,没有管理火星。听到这个消息,具备集结力的兰姐姐立刻找来了N个火星蘑菇战士,并给了他们兰机甲,让他们去对付沙兵部队。
    但是,火星蘑菇战士是需要鼓励的,他们需要钱,而且他们很懒。
    有M个克隆人,第i个血量为ai。而N个火星蘑菇战士中,第i个的战斗力为bi。当一个兰机甲的战斗力大于一个克隆人的血量时,这个兰机甲可以放出兰波,打爆这个克隆人。
    不过,一个火星蘑菇战士只愿意出战一次,且第i个战士出战需要付bi的价格(即一个兰机甲的战斗力与它的出战价格一致)。兰姐姐智商不低(gao),她不会派遣一个火星蘑菇战士与一个他打不过的克隆人打。
   现在兰姐姐问你,如何分配使得她所付钱最少,且能够击爆所有克隆人。她结局烂不烂就决定在你手里。

输入

    第一行,两个正整数N,M
    第二行,N个数表示各个兰机甲的攻击力。
    第三行,M个数表示各个克隆人的血量。

输出

一个数表示最少花费多少钱能够击爆所有克隆人,若无论如何都无法击爆所有克隆人,则输出-1.

样例输入输出

输入#1 复制
6 3
2 9 4 6 7 3
1 4 8
输出#1 复制
17

提示

【样例解释】
兰姐姐应派遣攻击力分别为2、6、9的兰机甲,去分别击燥血量为1、4、8的克隆人。
【数据范围】
  10%,沙兵部队保存实力,兰姐姐存款也不多。N<=5, M <=5;
  40%,兰姐姐向姐姐Horse countryxing借了-些火星币,买了许多兰机甲,N<=20, M<=5;
  70%,沙兵部队被激怒,全军出击,N<=1000, M<=100 ;
  100%,兰姐姐毫不示弱,雇佣了更加多的蘑菇战士,N<=20000, M<=100.
由于克隆人较初级,而且兰机甲太烂,所以所有攻击值与血量都小于500000 ,克隆人血量两两不同,兰机甲攻击力也两两不同。

序号 标题 作者 发表时间 费用 订购数 操作