我還是抄解題報告的，感覺想法很妙

      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;
}