AT_bogosortcontest_div1_h Please Insert Coin

縦 $ H $ マス、横 $ W $ マスのグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i, j) $ とします。 各マス $ (i,j) $ には、そのマスにブロックが配置される時刻を表す整数 $ A_{i,j} $ が書かれています。 時刻は $ 1 $ から $ K = \max(A_{i,j}) $ まで進みます。配列 $ A $ は以下の性質を満たします。 - $ 1 \leq k \leq K $ を満たす任意の整数 $ k $ について、 $ A_{i,j} = k $ となるマスが少なくとも $ 1 $ つ存在する。 - 同じ値 $ k $ を持つマスの集合は、上下左右に連結している。 - ブロックは各列で下から順に積まれる。すなわち、任意の $ 1 \leq i \leq H-1 $ と $ 1 \leq j \leq W $ に対して $ A_{i+1, j} \leq A_{i, j} $ が成り立つ。 ある時刻において、列 $ j $ に積み上がっているブロックの個数を $ h_j $ とします。初期状態ではすべての列で $ h_j = 0 $ です。 soryuusi 君は初期状態において列 $ s $ にいます。 時刻 $ k = 1, 2, \dots, K $ に対して、順に以下のようにゲームが進行します。 1. **soryuusi 君の移動**：soryuusi 君はグリッド内の左右に隣接する列へ $ 1 $ 列ずつ、任意の回数だけ移動することができる（移動せず現在の列に留まることも可能である）。 列 $ x $ から隣接する列 $ y $ へ $ 1 $ 列移動するごとに、その時点でのブロックの高さを用いて $ |h_x - h_y| + 1 $ のスタミナを消費する。 2. **ブロックの配置**： $ A_{i,j} = k $ となるすべてのマスにブロックが配置され、該当する列の $ h_j $ が配置されたブロックの個数分だけそれぞれ増加する。 このとき、soryuusi 君が現在いる列に $ 1 $ つでも新たにブロックが配置された場合、soryuusi 君は押し潰されてゲームオーバーとなる。 時刻 $ K $ のブロックの配置が終了するまで soryuusi 君がゲームオーバーにならずに生き残ることができるか判定し、可能な場合は消費するスタミナの合計の最小値を求めてください。生き残ることが不可能な場合は `-1` を出力してください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ H $ $ W $ $ s $ $ A_{1,1} $ $ A_{1,2} $ $ \dots $ $ A_{1,W} $ $ A_{2,1} $ $ A_{2,2} $ $ \dots $ $ A_{2,W} $ $ \vdots $ $ A_{H,1} $ $ A_{H,2} $ $ \dots $ $ A_{H,W} $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースについて、消費するスタミナの最小値を出力せよ。ただし、生き残ることが不可能な場合は `-1` を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、soryuusi 君は以下のように行動することで、消費スタミナ $ 10 $ を達成できます。 - $ 4 $ 列目に移動する。 $ (|0 - 0| + 1) + (|0 - 0| + 1) + (|0 - 0| + 1) = 3 $ のスタミナを消費する。 - 時刻 $ 1 $ のブロックが配置される。 - $ 2 $ 列目に移動する。 $ (|0 - 1| + 1) + (|1 - 2| + 1) = 4 $ のスタミナを消費する。 - 時刻 $ 2 $ のブロックが配置される。 - $ 4 $ 列目に移動する。 $ (|2 - 2| + 1) + (|2 - 3| + 1) = 3 $ のスタミナを消費する。 - 時刻 $ 3 $ のブロックが配置される。 消費スタミナ $ 9 $ 以下で生き残ることは不可能なので、消費スタミナの最小値は $ 10 $ です。  $ 2 $ つ目のテストケースについて、soryuusi 君はどのように行動しても、時刻 $ 2 $ のブロックの配置を回避することはできません。したがって、このテストケースに対する出力は `-1` となります。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 1 \leq H, W $ - $ H \times W \leq 5 \times 10^5 $ - $ 1 \leq s \leq W $ - $ 1 \leq A_{i,j} \leq H \times W \ (1 \leq i \leq H, 1 \leq j \leq W) $ - $ 1 \leq k \leq K $ を満たす任意の整数 $ k $ について、 $ A_{i,j} = k $ となるマス $ (i,j) $ が少なくとも $ 1 $ つ存在する - $ A_{i,j} = k $ となるマス $ (i,j) $ の集合は、上下左右に連結している - $ A_{i+1, j} \leq A_{i, j} \ (1 \leq i \leq H-1, 1 \leq j \leq W) $ - すべてのテストケースについての $ H \times W $ の総和は $ 5 \times 10^5 $ 以下 - 入力される数値はすべて整数