10536: 竞赛
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:0
Description
XX年XX月的某一天,阿狸到黑森林里去玩,不幸被野兽们抓了起来。去觐见动物王国的领袖——巨龙。
动物王国的动物们很不和谐,动不动就会来个决斗,而决斗所破坏掉的森林资源自然全部要国王掏腰包。巨龙知道狐狸是最聪明的【其实是狡猾】,他答应如果阿狸能安排动物们的挑战组合,就答应放了他。
动物们的决斗很有规律,他们分为两个阵营,决斗开始时两个阵营的动物排成两个队,每个动物有一个破坏值,然后由阿狸来安排比赛,动物们会按照顺序分组进行PK,可以是单挑,群挑,或者是单挑群。具体规则如下:
从后往前,每次从A阵营选出连续k1(k1>0)个动物,他们的破坏值之和为S1,从B阵营选出连续k2(k2>0)个动物,他们的破坏值之和为S2,选出的这些动物将进行决斗,这次破坏导致森林的修整费用为 (S1-K1)*(S2-K2)。决斗直到两个队伍都为空时结束。结束之后,这些决斗的总修整费用就为每次PK修整费用的和。
阿狸的大脑一片空白,只能让你来完成任务救出阿狸。你需要做的就是使这次决斗的费用最小。
动物王国的动物们很不和谐,动不动就会来个决斗,而决斗所破坏掉的森林资源自然全部要国王掏腰包。巨龙知道狐狸是最聪明的【其实是狡猾】,他答应如果阿狸能安排动物们的挑战组合,就答应放了他。
动物们的决斗很有规律,他们分为两个阵营,决斗开始时两个阵营的动物排成两个队,每个动物有一个破坏值,然后由阿狸来安排比赛,动物们会按照顺序分组进行PK,可以是单挑,群挑,或者是单挑群。具体规则如下:
从后往前,每次从A阵营选出连续k1(k1>0)个动物,他们的破坏值之和为S1,从B阵营选出连续k2(k2>0)个动物,他们的破坏值之和为S2,选出的这些动物将进行决斗,这次破坏导致森林的修整费用为 (S1-K1)*(S2-K2)。决斗直到两个队伍都为空时结束。结束之后,这些决斗的总修整费用就为每次PK修整费用的和。
阿狸的大脑一片空白,只能让你来完成任务救出阿狸。你需要做的就是使这次决斗的费用最小。
Input
第一行两个正整数L1,L2分别表示两阵营的人数;
第二行L1个正整数,描述A阵营每个人的破坏值。
第三行L2个正整数,描述B阵营每个人的破坏值。
第二行L1个正整数,描述A阵营每个人的破坏值。
第三行L2个正整数,描述B阵营每个人的破坏值。
Output
一个正整数表示森林的最小修整费用
Sample Input Copy
3 2
1 2 3
1 2
Sample Output Copy
2
HINT
【样例解释】
从后往前数,A中的3和B中的2进行PK,这次的破坏值为:(3-1)*(2-1)=2,然后A中的1,2和B中的1进行PK,这次的破坏值为:(3-1)*(1-1)=0,所以这组数据的结果为2+0=0。
【数据范围】
1<=L1,L2<=2000
从后往前数,A中的3和B中的2进行PK,这次的破坏值为:(3-1)*(2-1)=2,然后A中的1,2和B中的1进行PK,这次的破坏值为:(3-1)*(1-1)=0,所以这组数据的结果为2+0=0。
【数据范围】
1<=L1,L2<=2000