Problem Q
Reseplanering

Alice och Bob tillbringar den här sommaren med att noga planera inför nästa sommar. De hade tänkt resa från den gamla staden A-holm till den populära semesterorten B-stad, men de har inte bestämt sig för vilka orter de ska besöka på vägen. Det finns totalt $N$ orter de kan besöka, numrerade från $1$ till $N$. A-holm är ort nummer $1$ och B-stad är ort nummer $N$. Mellan vissa par av orter finns det enkelriktade vägar, och det kan finnas flera vägar mellan samma par av orter.

Alice och Bob befinner sig just nu i A-holm. Varje dag väljer de var de ska resa härnest genom att likformigt slumpmässigt välja en av de enkelriktade vägar som går från orten de befinner sig i. När de kommer fram till B-stad så stannar de.

Alice och Bob skulle vilja boka in hemresan på en dag när det är $95\% $ sannolikt att de kommit fram till B-stad. Och de menar verkligen exakt $95\% $, varken mer eller mindre! Dessutom finns ett $10$-dagarsfönster när tågbiljetter hem är extra billiga, och om hemresedagen inte är i detta fönster så kan de lika gärna skippa resan helt och hållet.

Du får givet ett positivt heltal $L$, och ska hitta ett tal $T$ som uppfyller $L \leq T \leq L + 9$, sådant att sannolikheten att Alice och Bob befinner sig i B-stad efter att ha gjort $T$ stycken resor är exakt $95\% $. Om det finns flera $T$ som uppfyller detta ska du hitta det minsta av dem.

Indata

Den första raden innehåller två heltal $N$ och $L$ ($2 \leq N \leq 100$, $1 \leq L \leq 10^6$).

De följande $N$ raderna innehåller $N$ heltal vardera. Det $j$:te talet på den $i$:te raden $a_{ij}$ indikerar att det finns $a_{ij}$ enkelriktade vägar från ort $i$ till ort $j$ ($0 \leq a_{ij} \leq 10^9$).

Det kommer inte finnas några vägar från en ort till sig själv, och det finns inga vägar som går från B-stad (dvs. ort nummer $N$). I alla städer förutom B-stad kommer det finnas minst en utgående väg, så det är alltid möjligt för Alice och Bob att välja en väg.

Utdata

Skriv ut ett heltal $T$ så som beskrivs i uppgiften. Om det inte finns någon lösning, skriv ut $-1$.

3 1
0 11 9
1 0 10
0 0 0

2

4 3
0 1 0 19
0 0 2 0
0 5 0 3
0 0 0 0

-1

3 100
0 1 0
1 0 0
0 0 0

-1