我还是抄解题报告的，感觉想法很妙

      http://blog.sina.com.cn/s/blog_5123df350100h3bu.html

           
/*
    题目大意：给定N维空间的一些点，求加权曼哈顿距离最近的两个点的距离。
    分析： 权值可以乘到点坐标上去，就是说可以把每个点每一维都乘上对应的w[t]。
    考虑2维的情况 |x1-x2|+|y1-y2| 最大值只有4种情况：
    (x1+y1)-(x2+y2) , (-x1+y1)-(-x2+y2), (-x1-y1)-(-x2-y2), (x1-y1)-(x2-y2)，
    最大值是4种之一，这里面取最大就可以了。
    尽一步看到4种形式，每种自身第一个点和第二个点坐标间加正负号的方法是一样的。
    推广到N维，我们枚举加符号的方式，一共（1<<M）种，然后对每种方式，
    每个点的坐标按枚举的加括号的方式N维运算求出一个值来，取最大和最小值的差，
    作为可能结果，最后取所有差值中最大的即可。（注意M很小，只有8）复杂度O(2M*n)
*/
#include<cstdio>
#include<cstring>
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)

const int MAXN=50001;
const int M=9;
const int inf=1000000000;

int cb[MAXN][M],w[M];
int n,m;

int main(){
    while(~scanf("%d%d",&n,&m)){

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&cb[i][j]);
        for(int j=1;j<=m;j++)
            scanf("%d",&w[j]);

        int limit=1<<m,ans=0;
        for(int k=0;k<limit;k++){
            int Max=-inf,Min=inf;
            for(int i=1;i<=n;i++){
                int tmp=0;
                for(int t=0;t<m;t++){
                    if(k&(1<<t))tmp+=w[t+1]*cb[i][t+1];
                    else tmp-=w[t+1]*cb[i][t+1];
                }
                Max=max(tmp,Max);
                Min=min(tmp,Min);
            }
            ans=max(ans,Max-Min);
        }
        printf("%d\n",ans);
    }
    return 0;
}