问题 4581 --I、锴哥堆积木

4581: I、锴哥堆积木

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

话说锴哥小时候很喜欢玩积木,精通各种积木的玩法。

我们现在回溯到锴哥小时候,有一天,锴哥突发奇想,要用1*1*1的小方块自己做一套积木,于是锴哥精心绘制了新积木每个部件的三视图,规格都是N*N。可是,不幸却发生了,锴哥的图纸有两张不翼而飞,只剩下顶视图。锴哥当然不会善罢甘休,他用传说中随机算法,生成了一张N*N的数表,表示最底层木块的价值,对于竖直方向的木块的价值,由下到上按公差为D = —max(i,j)成等差数列,i、j表示数表中某位置的的横纵坐标(1<= i <= N ,1<= j <= N)。锴哥现在要按照顶视图把价值最大的积木选出来,显然这是唯一确定的,并称这个价值为锴氏价值。当然了,积木必须是完整的,为此锴哥买了胶水去把相互接触的小方块表面用胶水粘起来。由于把每两个小正方体面粘起来的花费是固定的C,锴哥立即就能算出胶水的总花费。但锴哥有很多有很多图纸,所以请你来帮锴哥解答。

样例:

结果不会超过int的范围。

输入

第一行包含一个整数T(1<=T<=20),表示测试数据组数。

对于每次测试数据,包含若干行。

第一行给出两个数N(1<=N<=50)和C(1<=N<=10)表示数表规模和花费。

接下来N行给出一个N*N的数表,表示锴哥的随机数表,表示(i,j)位置的随机数。

然后N行给出一个或积木部件顶视图,表示(i,j)位置竖直方向的方块数。

输出

对于每组测试数据输出一行,包含两个数。分别表示锴哥所制作积木的的锴氏价值和总花费,用空格隔开。

样例输入

1
2 3
4 5
6 7
1 2
0 1

样例输出

19 9

来源

[提交][状态]