問題文

縦横それぞれが NN マスの,N×NN \times N マスからなるグリッドがあります.
はじめ,上から ii 行目,左から jj 列目のマス (i,j)(i,j) には整数 Ai,jA_{i,j} が書かれています.

MojaMoja 君は不平等なことが嫌いなので,このグリッドに書かれている整数をなるべく均一にしたいです.
そこで,Increaser という機械を作りました.

はじめ,マス (1,1)(1, 1) に Increaser が置かれています.
その後,次の操作を 00 回以上繰り返し行うことができます.

  • Increaser に対して,以下のうちいずれか一方を行わせる
    • すべてのマスより一つを選び,そのマスに移動する
    • そのときにいるマスに書かれている整数を 11 だけ増加させる

TT 個のテストケースが与えられます.
t(1tT)t \scriptsize \hspace{0.3em} (1 \leq t \leq T) 個目のテストケースでは,K=KtK=K_t として次の問題を解いてください.

  • 操作を KK 回まで行えるとする.
  • 操作後,各マスに書かれている整数の分布の範囲,すなわち max1i,jNAi,jmin1i,jNAi,j\max \limits_{1 \leq i,j \leq N} A_{i,j} - \min \limits_{1 \leq i,j \leq N} A_{i,j} をグリッドの起伏として得る.
  • KK 回以内の操作によって得られる起伏の最小値を求めよ.

制約

  • 1T1041 \leq T \leq 10^4
  • 1N10001 \leq N \leq 1000
  • Ai,j109(1i,jN)|A_{i,j}| \leq 10^9 \hspace{0.3em} \scriptsize (1 \leq i, j \leq N)
  • 0Kt109(1tT)0 \leq K_t \leq 10^9 \hspace{0.3em} \scriptsize (1 \leq t \leq T)
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる.

NTN \hspace{0.5em} T
A1,1A1,2A1,NA_{1,1} \hspace{0.5em} A_{1,2} \ldots A_{1,N}
A2,1A2,2A2,NA_{2,1} \hspace{0.5em} A_{2,2} \ldots A_{2,N}
\vdots
AN,1AN,2AN,NA_{N,1} \hspace{0.5em} A_{N,2} \ldots A_{N,N}
K1K_1
K2K_2
\vdots
KTK_T

出力

TT 行出力せよ.
t(1tT)t \scriptsize \hspace{0.3em} (1 \leq t \leq T) 行目には tt 個目のテストケースに対する答えを出力せよ.

サンプル

入力例1
4 5
5 -2 2 1
1 2 5 1
2 3 5 2
2 4 0 2
3
5
17
36
0
出力例1
5
5
3
2
7

33 回まで操作を行えるとき,11 回目の操作でマス (1,2)(1, 2) へ移動し,残り 22 回の操作でそのマスに書かれている数値を 22 だけ増加させることができます.
このとき,50=55 - 0 = 5 の起伏を得ることができます.
どのように操作を行っても,33 回以内に 55 より真に小さい起伏は得られないため,これが最小です.

提出


Go (1.21)