La ferme de Farmer John peut être représentée par un graphe orienté pondéré, avec des routes (arêtes) reliant différents sommets, le poids de chaque arête étant le temps nécessaire pour parcourir la route. Chaque jour, Bessie aime aller de la grange (située au sommet $1$) aux champs (situés au sommet $N$) en empruntant exactement $K$ routes, et veut atteindre les champs le plus vite possible sous cette contrainte. Cependant, à un certain moment, les routes cessent d'être entretenues et se dégradent une à une, devenant impraticables. Aidez Bessie à trouver le plus court chemin de la grange aux champs à tout instant !

Formellement, on part d'un graphe orienté pondéré complet à $N$ sommets ($1\le N\le 300$) et $N^2$ arêtes : une arête pour chaque paire $(i, j)$ avec $1 \le i, j \le N$ (notez qu'il y a $N$ boucles). Après chaque suppression, affichez le poids minimal d'un chemin de $1$ à $N$ qui emprunte exactement $K$ arêtes, pas nécessairement distinctes ($2\le K\le 8$). Notez qu'après la $i$-ième suppression, il reste $N^2-i$ arêtes dans le graphe.

Le poids d'un chemin est défini comme la somme des poids de toutes ses arêtes. Notez qu'un chemin peut emprunter plusieurs fois la même arête et passer plusieurs fois par le même sommet, y compris les sommets $1$ et $N$.

Entrée

La première ligne contient $N$ et $K$.

Les $N$ lignes suivantes contiennent chacune $N$ entiers. Le $j$-ième entier de la $i$-ième ligne est $w_{ij}$ ($1\le w_{ij}\le 10^8$).

Suivent $N^2$ lignes supplémentaires, chacune contenant deux entiers $i$ et $j$ ($1\le i,j\le N$). Chaque paire d'entiers apparaît exactement une fois.

Sortie

Exactement $N^2$ lignes, contenant le poids minimal d'un chemin à $K$ arêtes après chaque suppression. Si aucun chemin à $K$ arêtes n'existe, affichez $-1$.

Exemples

Entrée 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

Sortie 1

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

Remarque

Après la première suppression, le plus court chemin à $4$ arêtes est :

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

Après la deuxième suppression, le plus court chemin à $4$ arêtes est :

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

Après la troisième suppression, le plus court chemin à $4$ arêtes est :

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

Après six suppressions, il n'existe plus de chemin à $4$ arêtes.

Sous-tâches

• Pour $2\le T\le 14$, le cas de test $T$ vérifie $K=\lfloor (T+3)/2\rfloor$.

Auteur du problème : Benjamin Qi