题意：

给出一堆n个东西和另一堆m个东西，每个东西有一个分数S和k个属性值。让你在n个东西和m个东西里各选一件，使$S_{nw}+S_{mw}+\sum_{i=1}^k|x_{nw}[i]-x_{mw}[i]|$最大。其中$K<=5, \sum(n+m)<=300000$。

思路：

想到了多维曼哈顿距离…然而想到了之前做过的一道从一堆点里选一个点让其他点到它的曼哈顿距离最短的那道题…怎么会想到那道题呢…明显是不同的东西啊…

S的部分是好处理的，考虑绝对值求和部分。

考虑最简单的情况，k=2：

$|x_1-x_2|+|y_1-y_2|$把绝对值去掉，有四种情况：

$x_1-x_2+y_1-y_2，x_1-x_2-y_1+y_2，-x_1+x_2+y_1-y_2,-x_1+x_2-y_1+y_2$，

把$(x_1,y_1)，(x_2,y_2)$提出来，有

$(x_1+y_1)-(x_2+y_2)，(x_1-y_1)-(x_2-y_2)，(-x_1+y_1)-(-x_2+y_2)，(-x_1-y_1)-(-x_2-y_2)$。

所以只要二进制枚举符号，n个东西里取S+k维曼哈顿距离最大的，m个东西里取-S+k维曼哈顿距离最小的，相减来更新答案就可以了。复杂度为$O(2^k*k*n)$。

代码：

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
ll ns[100010];
ll nx[100010][10];
ll ms[100010];
ll mx[100010][10];
ll nn[100010],mm[100010];
int main()
{
    int t,n,m,num;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&num);
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&ns[i]);
            for(int j=0;j<num;j++)
                scanf("%lld",&nx[i][j]);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%lld",&ms[i]);
            for(int j=0;j<num;j++)
                scanf("%lld",&mx[i][j]);
        }
        ll ans=-INF;
        for(int i=0;i<(1<<num);i++)
        {
            for(int j=0;j<n;j++)
                nn[j]=ns[j];
            for(int j=0;j<m;j++)
                mm[j]=-ms[j];
            for(int j=0;j<num;j++)
            {
                //printf("%d",i>>j&1);
                if((i>>j&1)==1)//+
                {
                    for(int k=0;k<n;k++)
                        nn[k]+=nx[k][j];
                    for(int k=0;k<m;k++)
                        mm[k]+=mx[k][j];
                }
                else
                {
                    for(int k=0;k<n;k++)
                        nn[k]-=nx[k][j];
                    for(int k=0;k<m;k++)
                        mm[k]-=mx[k][j];
                }
            }
            //printf("\n");
            ll MAX=-INF,MIN=INF;
            for(int j=0;j<n;j++)
                MAX=max(MAX,nn[j]);
            for(int j=0;j<m;j++)
                MIN=min(MIN,mm[j]);
            ans=max(ans,MAX-MIN);
        }
        printf("%lld\n",ans);
    }
    return 0;
}