Farmer John の農場は有向重み付きグラフで表せます。道路（辺）が頂点同士を結び、各辺の重みはその道路を通るのに必要な時間です。Bessie は毎日、納屋（頂点 $1$）から畑（頂点 $N$）までちょうど $K$ 本の道路を通って移動し、この制約のもとでできるだけ早く畑に着きたいと思っています。しかし、ある時点から道路が整備されなくなり、1 本ずつ壊れて通行不能になっていきます。それぞれの時点で、納屋から畑までの最短経路を求めて Bessie を助けてください！

厳密には、最初に $N$ 頂点（$1\le N\le 300$）、$N^2$ 辺の完全有向重み付きグラフがあります。各組 $(i, j)$（$1 \le i, j \le N$）に対して辺が 1 本あります（自己ループが $N$ 本あることに注意してください）。各辺の削除後に、頂点 $1$ から頂点 $N$ までちょうど $K$ 本の辺（異なる辺である必要はありません）を通る経路（$2\le K\le 8$）の重みの最小値を出力してください。$i$ 回目の削除後には、グラフに $N^2-i$ 本の辺が残っています。

経路の重みは、経路上のすべての辺の重みの総和と定義します。同じ辺や同じ頂点を複数回通ってもよく、頂点 $1$ や $N$ も例外ではありません。

入力

1 行目には $N$ と $K$ が与えられます。

続く $N$ 行には、それぞれ $N$ 個の整数が与えられます。$i$ 行目の $j$ 番目の整数は $w_{ij}$（$1\le w_{ij}\le 10^8$）です。

さらに $N^2$ 行が続き、各行には 2 つの整数 $i$ と $j$（$1\le i,j\le N$）が与えられます。整数の各組はちょうど 1 回ずつ現れます。

出力

ちょうど $N^2$ 行に、各削除後の $K$ 本の辺を通る経路の重みの最小値を出力してください。そのような経路が存在しない場合は $-1$ を出力してください。

入出力例

入力 1

3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2

出力 1

11
18
22
22
22
-1
-1
-1
-1

注記

1 回目の削除後、$4$ 本の辺を通る最短経路は次のとおりです。

1 -> 2 -> 3 -> 2 -> 3

2 回目の削除後、$4$ 本の辺を通る最短経路は次のとおりです。

1 -> 3 -> 2 -> 1 -> 3

3 回目の削除後、$4$ 本の辺を通る最短経路は次のとおりです。

1 -> 3 -> 3 -> 3 -> 3

6 回削除した後は、$4$ 本の辺を通る経路は存在しません。

小課題

• $2\le T\le 14$ に対し、テストケース $T$ は $K=\lfloor (T+3)/2\rfloor$ を満たします。

問題作成：Benjamin Qi