比赛

Grade 0 Open Time Friday, 5 October 2012, 3:25 pm
Discount 0.8 Time Discount Friday, 5 October 2012, 3:25 pm
Allow late Yes Close Time Friday, 5 October 2012, 3:25 pm
Input file Pk.in Output file Pk.out

题目描述

     新兵们一般在部队没什么娱乐活动,而且还老有个警官在旁边即即歪歪,所以他们总要找个法子发一下怒气,所以有时候两个不同营的新兵就喜欢一起打架。。。。。。 A营和B营就是典型的例子。而且他们破坏力很大,常常把操场打得这里坑一块那里坑一块,警官很头疼,因为都要他掏腰包。。。。。。

     为了减少损失,他决定每隔一段时间由他自己组织搞次比赛(打架)。

     比赛开始时两个营新兵排成两个队,每个士兵有一个破坏值,然后由警官来安排比赛的人,分任意次来PK,可以是单挑,群挑,或者是单挑群(呵呵,警官只在乎修整费用最少)具体规则如下:

从后往前,每次从A营选出连续k1(k1>0)个人,从B营选出连续k2k2>0)个人进行pk。那么这次破坏导致操场的修整费用为 (S1-K1)*(S2-K2)。比赛直到两个队伍都为空时结束。而这次比赛的总修整费用就为每次PK修整费用的和。

警官拜托你的是使这次比赛的费用最小。

    

输入数据

    第一行两个正整数L1,L2分别表示两营的人数;

第二行L1个正整数,描述A 营每个人的破坏值

第三行L2个正整数,描述B 营每个人的破坏值

     1<=L1,L2<=2000

输出数据

一个正整数表示操场的最小修整费用

 

 

样例输入

3 2

1 2 3

1 2

 

样例输出

2