OI题库

题目描述

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

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

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

从后往前，每次从A营选出连续k1(k1>0)个人，从B营选出连续k2（k2>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