Farmer Johns Farm lässt sich als gerichteter, gewichteter Graph darstellen, in dem Straßen (Kanten) verschiedene Knoten verbinden und das Gewicht jeder Kante der Zeit entspricht, die man zum Befahren der Straße benötigt. Jeden Tag möchte Bessie von der Scheune (bei Knoten $1$) zu den Feldern (bei Knoten $N$) gelangen, dabei genau $K$ Straßen benutzen und unter dieser Bedingung die Felder so schnell wie möglich erreichen. Irgendwann werden die Straßen jedoch nicht mehr instand gehalten und verfallen nach und nach, sodass sie unpassierbar werden. Hilf Bessie, zu jedem Zeitpunkt den kürzesten Weg von der Scheune zu den Feldern zu finden!

Formal beginnen wir mit einem vollständigen gewichteten gerichteten Graphen mit $N$ Knoten ($1\le N\le 300$) und $N^2$ Kanten: eine Kante für jedes Paar $(i, j)$ mit $1 \le i, j \le N$ (beachte, dass es $N$ Schleifen gibt). Gib nach jeder Entfernung das minimale Gewicht eines Weges von $1$ nach $N$ aus, der genau $K$ (nicht notwendigerweise verschiedene) Kanten durchläuft ($2\le K\le 8$). Beachte, dass nach der $i$-ten Entfernung noch $N^2-i$ Kanten im Graphen verbleiben.

Das Gewicht eines Weges ist als Summe der Gewichte aller Kanten auf dem Weg definiert. Beachte, dass ein Weg dieselbe Kante und denselben Knoten mehrfach enthalten darf, einschließlich der Knoten $1$ und $N$.

Eingabe

Die erste Zeile enthält $N$ und $K$.

Die nächsten $N$ Zeilen enthalten jeweils $N$ ganze Zahlen. Die $j$-te ganze Zahl in der $i$-ten Zeile ist $w_{ij}$ ($1\le w_{ij}\le 10^8$).

Danach folgen $N^2$ weitere Zeilen mit jeweils zwei ganzen Zahlen $i$ und $j$ ($1\le i,j\le N$). Jedes Zahlenpaar kommt genau einmal vor.

Ausgabe

Genau $N^2$ Zeilen: das minimale Gewicht eines Weges mit $K$ Kanten nach jeder Entfernung. Falls kein Weg mit $K$ Kanten existiert, gib $-1$ aus.

Beispiele

Eingabe 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

Ausgabe 1

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

Hinweis

Nach der ersten Entfernung ist der kürzeste Weg mit $4$ Kanten:

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

Nach der zweiten Entfernung ist der kürzeste Weg mit $4$ Kanten:

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

Nach der dritten Entfernung ist der kürzeste Weg mit $4$ Kanten:

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

Nach sechs Entfernungen gibt es keinen Weg mit $4$ Kanten mehr.

Teilaufgaben

• Für $2\le T\le 14$ erfüllt Testfall $T$ die Bedingung $K=\lfloor (T+3)/2\rfloor$.

Autor der Aufgabe: Benjamin Qi