Problem Description
给你一个N*N的方格,里面都是非负整数(小于32768),我们定义这个方格的总和为:其中的任何一个S*S(1<=S<=N)的子方格中的数字的总和。由于中间有K(0<=K<=N*N)个单位方格中的数字是0,因此现在给定你M(K<=M&&M<=10000)个正整数(小于32768),你可以从中选择K个,来填入原来的N*N的值为0的单位方格中,从而最大化的增加我们定义的方格的总和。
Input
这里有T组测试数据,第一行输入T,T<=100。对于测试数据,先输入一个N(N<=30),然后输入一个N*N的矩阵,中间含0的元素,然后给定一个M,后一行输入M个正整数。
Output
对于每组测试数据,输出能够最大的增加的值。
Sample Input
1
3
1 2 3
4 0 2
0 2 7
4
2 9 4 7
Sample Output
75