随机化算法！！！
中位数可以二分，把(a_{i,j}leq mid)赋为-1，否则为1，若DP最小值后(leq0)则可以继续往更小的地方DP
假设我们已经知道答案了，(kleq5)又要最小代价联通，斯坦纳树！
我们可以把每个颜色随机放入(k)个盒子，每个盒子选一个，那么至少有(k)种颜色
每次成功的概率为(frac{k!k^{col-k}}{k^{col}}=frac{k!}{k^k})，col为总颜色数
次成功概率为(1-(1-frac{k!}{k^k})^T)，200次后就非常高了
步骤：
- 随机
- 二分
- 检查（两个DP数组，第一个为个数（先保证个数，每次DP一定不变），第二个为关于中位数的那个）
#include<bits/stdc++.h>
using namespace std;
mt19937 gen(chrono::steady_clock().now().time_since_epoch().count());
#define rand(r) (uniform_int_distribution<int>(1, r)(gen))
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=240,inf=0x3f3f3f3f;
int n,m,k,cn,num,mn,mk,ans1,ans2;
int b[N],bel[N],vis[N],a[N][N],c[N][N],d[N][N],f[N][40],g[N][40];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
queue<int>q;
inline bool upt(int x,int s,int ff,int gg){
if(ff<f[x][s]||(ff==f[x][s]&&gg<g[x][s])){
f[x][s]=ff;g[x][s]=gg;
return 1;
}
return 0;
}
inline int id(int i,int j){
return (i-1)*m+j;
}
inline bool check(int mid){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j]=(a[i][j]<=mid)?-1:1;
memset(g,0x3f,sizeof(g));
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)if(c[i][j]!=-1){
f[id(i,j)][1<<bel[c[i][j]]-1]=1;
g[id(i,j)][1<<bel[c[i][j]]-1]=d[i][j];
}
for(int s=1,S=(1<<k),x,y,u,v,nx,ny;s<S;s++){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
x=id(i,j);
for(int sta=(s-1)&s;sta;sta=(sta-1)&s)
upt(x,s,f[x][sta]+f[x][s^sta]-1,g[x][sta]+g[x][s^sta]-d[i][j]);
if(f[x][s]!=inf){q.push(x);vis[x]=1;}
}
while(!q.empty()){
u=q.front();q.pop();
vis[u]=0;
y=u%m;if(!y)y=m;
x=(u-y)/m+1;
for(int i=0;i<4;i++){
nx=x+dx[i];ny=y+dy[i];
v=id(nx,ny);
if(nx<1||nx>n||ny<1||ny>m||c[nx][ny]==-1)continue;
if(upt(v,s,f[u][s]+1,g[u][s]+d[nx][ny])&&!vis[v]){q.push(v);vis[v]=1;}
}
}
}
num=mn=inf;
for(int i=1,s=(1<<k)-1,x;i<=n;i++)
for(int j=1;j<=m;j++){
x=id(i,j);
if(f[x][s]<num||(f[x][s]==num&&g[x][s]<mn)){
num=f[x][s];mn=g[x][s];
}
}
return mn<=0;
}
inline void stn(){
for(int i=1;i<=mk;i++)bel[i]=rand(k);
static int l,r,mid;
l=1;r=cn;
while(l<r){
mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
if(num<ans1||(ans1==num&&r<ans2)){ans1=num;ans2=r;}
}
inline void solve(){
n=read();m=read();k=read();
mk=0;ans1=ans2=inf;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){c[i][j]=read();mk=max(mk,c[i][j]);}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)b[id(i,j)]=a[i][j]=read();
sort(b+1,b+n*m+1);
cn=unique(b+1,b+n*m+1)-b-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=lower_bound(b+1,b+cn+1,a[i][j])-b;
for(int T=150;T;T--)stn();
cout<<ans1<<" "<<b[ans2]<<"
";
}
int main(){
int T=read();
while(T--)solve();
return (0-0);
}