转载：http://hi.baidu.com/samroxas/item/da6159cb9bf42f28ee4665e1
描述 Description
在某年某月某日，小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想要代价最少，所以他向你求助。
输入格式 Input Format
文件第一行为一个整数T，代表数据组数。
对于每个数据，第一行为两个整数n和m，意义如题目中所述。
接下来n-1行，每行一个整数，分别代表x1，x2，……xn-1。
接下来m-1行，每行一个整数，分别代表y1，y2，……ym-1。
输出格式 Output Format
对于每个数据输出一行，该行包含一个整数为最小代价。
样例输入
1
6 4
2
1
3
1
4
4
1
2
样例输出
42
哭了。。。本来基本的贪心思路是对的，每次先切最大的。结果一激动，每次取最大的时候比较成了变更之后的比较。。。其实就是每次且最初的代价最大的就好了。。。
贪心证明：简单的贪心。由于对于两条横线（或竖线），显然应当先切值大的会更优。对于一条横线和一条竖线，不妨设切横线的价值为x,设切竖线的价值为y,此时横线已切了A次，竖线已切了B次。若有x>y，则必有x*B+y*(A+1)<x*(B+1)+y*A。故对整体而言，按照从大到小的顺序切也会最优，所以将所有的值的排序后按照从大到小的顺序切过去就行。 该证明给出的是当本刀切X下刀切Y或者本刀切Y下刀切X的情况。但是，如果需要连着切呢？如X1，X2，X3都比Y1要大，我们把X1，X2，X3都切完再去切Y1这样是不是最优的呢？当然是，仍然是横切了A次，竖切了B次，
那么按照X1，X2，X3，Y1的顺序切的代价是：B*(X1+X2+X3)+(A+3)*Y1①
而按照其他顺序，如X1，Y1，X2，X3的顺序来切的代价为：B*X1+(B+1)*(X2+X3)+(A+1)*Y1②
用②式-①式可得：X2+X3-2Y1>0显然成立（因为X1，X2，X3均大于Y1）
Y1放在其它地方也同理可证X1，X2，X3，Y1这种顺序是最优的。X再多一点也一样，对于Y比较大的同理。所以贪心是正确的。
program vijos1745;
var
pp,timex,timey,q,restx,resty,headx,heady,t,n,m,i:longint;
y,x:array[1..10000] of longint;
ans:int64;
procedure exc(var i,j:longint);
var
k:longint;
begin
k:=i;
i:=j;
j:=k;
end;
procedure sortx(i,j:longint);
var
l,r,m:longint;
begin
l:=i;
r:=j;
m:=x[(i+j) div 2];
repeat
while x[i]>m do
inc(i);
while x[j]<m do
dec(j);
if i<=j then
begin
exc(x[i],x[j]);
inc(i);
dec(j);
end;
until i>j;
if i<r then
sortx(i,r);
if l<j then
sortx(l,j);
end;
procedure sorty(i,j:longint);
var
l,r,m:longint;
begin
l:=i;
r:=j;
m:=y[(i+j) div 2];
repeat
while y[i]>m do
inc(i);
while y[j]<m do
dec(j);
if i<=j then
begin
exc(y[i],y[j]);
inc(i);
dec(j);
end;
until i>j;
if i<r then
sorty(i,r);
if l<j then
sorty(l,j);
end;
begin
readln(t);
for q:=1 to t do
begin
fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
readln(n,m);
ans:=0;
for i:=1 to n-1 do
readln(x[i]);
for i:=1 to m-1 do
readln(y[i]);
if (n=1) and (m=1) then
begin
writeln(0);
continue;
end;
if n=1 then
begin
for i:=1 to m-1 do
ans:=ans+y[i];
writeln(ans);
continue;
end;
if m=1 then
begin
for i:=1 to n-1 do
ans:=ans+x[i];
writeln(ans);
continue;
end;
sortx(1,n-1);
sorty(1,m-1);//两个队，从大到小排序，每次比较两个队的队头，取较大的即可。
timex:=0;
timey:=0;
headx:=1;
heady:=1;
restx:=n-1;
resty:=m-1;
while (restx>0) or (resty>0) do
begin
if x[headx]>y[heady] then
begin
ans:=ans+x[headx]+timex*x[headx];//timex与timey表示行和列需要多切多少刀。。。
inc(timey);
inc(headx);
dec(restx);
end
else
begin
ans:=ans+y[heady]+timey*y[heady];
inc(timex);
inc(heady);
dec(resty);
end;
end;
writeln(ans);
end;
end.