G - Leveler MojaMoja

縦横それぞれが マスの， マスからなるグリッドがあります．
はじめ，上から 行目，左から 列目のマス には整数 が書かれています．

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

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

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

個のテストケースが与えられます．
個目のテストケースでは， として次の問題を解いてください．

• 操作を 回まで行えるとする．
• 操作後，各マスに書かれている整数の分布の範囲，すなわち をグリッドの起伏として得る．
• 回以内の操作によって得られる起伏の最小値を求めよ．

• 入力はすべて整数である

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

行出力せよ．
行目には 個目のテストケースに対する答えを出力せよ．

4 5
5 -2 2 1
1 2 5 1
2 3 5 2
2 4 0 2
3
5
17
36
0

5
5
3
2
7

回まで操作を行えるとき， 回目の操作でマス へ移動し，残り 回の操作でそのマスに書かれている数値を だけ増加させることができます．
このとき， の起伏を得ることができます．
どのように操作を行っても， 回以内に より真に小さい起伏は得られないため，これが最小です．