Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito tiene un nuevo juego en su celular. El juego consiste de $N$ islas conectadas por algunos puentes. El jugador debe ir de una isla $A$ hasta otra $B$ en el menor tiempo posible. Pasar por un puente tarda un segundo. El juego se complica al dividirse en $M$ niveles. Todos los niveles tienen las mismas $N$ islas y también coinciden $A$ y $B$. Lo que diferencia un nivel de otro son los puentes por los que puede pasar nuestro personaje. En todos los niveles es posible ir desde $A$ hasta $B$ pero tal vez no por el mismo camino. Otra peculiaridad del juego es que si en algún nivel escogemos un camino distinto al del nivel anterior, entonces obtenemos una penalización de K segundos debido a que el héroe se confunde fácilmente con el cambio. Fito tiene para cada nivel los puentes disponibles y quiere saber el menor tiempo total en que puede vencer todos los niveles.

La primera línea de la entrada tiene cinco enteros $N, M, A, B, K$ que describen la cantidad de islas $(2 \leq N \leq 50)$, la cantidad de niveles $(1 \leq M \leq 50)$, las islas donde comienza y termina el viaje y la penalización $(1 \leq K \leq 1000000)$ por cambiar de camino. Después le sigue la descripción de los $M$ niveles. Cada nivel es descrito por $N$ líneas con $N$ enteros cada uno. El entero $j$ de la línea $i$ es uno si hay un puente desde la isla $i$ a la isla $j$ disponible en ese nivel y cero en otro caso. Todos los puentes se pueden recorrer en las dos direcciones y nunca hay un puente desde una isla hacia ella misma.