/ Vijos / 题库 /

巧克力

巧克力

描述

在某年某月某日,小D莫名其妙的得到一块超级大的魔法巧克力,于是他决定将这块巧克力切成若干块送给幼儿园的其他小朋友。这是一块n*m的矩形巧克力,所以小D准备将它切成n*m块。

由于这块巧克力是一块魔法巧克力,所以必须按照特殊的方法进行切割。巧克力上共有n-1条横线和m-1条竖线,每次小D可以沿着其中的一条线切开某一块。而且这样切一次的代价只跟所切的线有关,而与所切的长度无关。沿着每条横线切一次的代价依次为y1,y2,……yn-1,竖线为x1,x2,……xm-1。

例如,对于图中的巧克力,我们先沿着3条横线切,再沿5条竖线切,最终代价为y1+y2+y3+4*(x1+x2+x3+x4+x5)。

图片
由于小D想要代价最少,所以他向你求助。

格式

输入格式

文件第一行为一个整数T,代表数据组数。

对于每个数据,第一行为两个整数n和m,意义如题目中所述。

接下来n-1行,每行一个整数,分别代表x1,x2,……xn-1。

接下来m-1行,每行一个整数,分别代表y1,y2,……ym-1。

输出格式

对于每个数据输出一行,该行包含一个整数为最小代价。

样例1

样例输入1

1
6 4
2
1
3
1
4
4
1
2

样例输出1

42

限制

每个测试点1s

提示

对于30%的数据,n<=100,m<=100,T<=10
对于100%的数据,n<=10000,m<=10000,T<=50

信息

ID
1745
难度
6
分类
贪心 点击显示
标签
(无)
递交数
859
已通过
248
通过率
29%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库

NOIP代码+思维

在下列比赛中:

Vijos2012年10月份月赛