背景

   absi2011在玩乐斗的时候遇到了一个木头人(老玩家知道的。。。。)这个木头人血非常非常多。。。。(lll6924:不是木头人都只有60多血么。。。。)(absi2011:这个是题目需要。。。。。)

描述

    absi2011遇到了个血可视作无穷大的木头人,木头人不会攻击,不会躲避。。。。absi2011的企鹅有n个武器和m个技能去攻击木头人。

    *****请注意,本题与实际游戏不同,游戏中的方案是纯随机的。

    absi2011的企鹅会听从absi2011的选择使用武器和技能。而absi2011一直犹豫不决,不知道该让企鹅使用什么武器或技能打,因为每个武器和技能都只能用一次于是给每个武器编上号分别为1....n,每个技能编上号分别为1...m。

    absi2011的企鹅的各个武器和技能的伤害在本题中是固定的。武器的为ai,技能的为bi。武器伤害保证为非负数,技能的伤害有可能是负数(有技能帮对方回血。。。)

    而这个游戏有意思就在这里:有时候会有(技能/武器)与(技能/武器)配合后,会产生意想不到的结果。(例如企鹅吼+胶水,会把对方打到死还无法出手,而三叉戟+幻影枪也许会出现秒杀对手的情况),所以我们对每对武器和武器一起使用的额外伤害设为cij,武器和技能一起使用的额外伤害为dij,技能和技能一起使用的额外伤害为eij。只要使用了就必须且必定能获得这个额外伤害(即使不连续)。

    保证cij=cji,cii=0,eij=eji,eii=0。由于前面的仅仅是辅助,后面的才能产生额外伤害,所以只能算一次

    absi2011要求你给出最大伤害值。

输入格式

  第一行两个整数n,m,如题目所述

  第二行n个整数ai,第三行m个整数bi

  下面n行n列是矩阵c,n行m列是矩阵d,m行m列是矩阵e

输出格式

  一个整数,最大伤害

样例输入

 2 1
 100 60
 0
 0 20
 20 0
 0
 0
 0

样例输出

 180

数据范围与约定

  保证对于100%的数据,0<=n,m<=1000,在三个矩阵中最多有10000个非零数字

  武器技能伤害均为整数且0<=ai<=1000,-1000<=bi<=1000

  0<=cij,dij,eij<=1000且均为整数

样例解释

  用上两个武器即可,伤害分别为100,60,共同伤害加成20,总伤害为180

  样例来源:absi2011的5级企鹅

Hint

  最后absi2011的企鹅无视了你给出的方案,使用神来一击把木头人打到1血然后再用一记短剑灭了它

  时限2s/点

来源

  fight.pet.qq.com