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

Fito tiene un nuevo juego en su teléfono. El juego consiste en un mapa donde aparecen $n$ ciudades y $m$ caminos que unen pares de ellas. El objetivo del juego consiste en transportar un tesoro desde una ciudad $s$ a otra $t$.

Los caminos que se pueden usar tienen varias características especiales. Lo primero es que cada camino se puede transitar en una sola dirección, y entre dos ciudades puede haber varios caminos distintos. Cada camino tiene un tiempo $t_{i}$ que indica cuánto se demora recorrerlo. En el juego existen ladrones que tratan siempre de robar el tesoro, por lo que cada camino requiere un mínimo de guardias $g_{i}$ que deben viajar por él para poder ser usado sin peligro de ataque. Por último en algunos caminos hay un puente por el que solo se puede pasar si se paga un diamante a su cuidador. Esta última propiedad fue añadida al juego para incentivar la compra de estos diamantes usando dinero real.

Al inicio de cada nivel, Fito tiene el mapa completo con todos los caminos posibles, la ciudad de salida y la de destino. También tiene una cantidad de diamantes y un tiempo máximo para completar el nivel. La jugada de Fito consiste en escoger la ruta que debe seguir la caravana, así como la cantidad de guardias que acompañarán el recorrido. Después de esto el juego simplemente sigue esta ruta y le dice a Fito si se pudo completar el nivel con las condiciones dadas. El tiempo para completar el nivel solo cuenta lo que se demora el tesoro siguiendo la ruta de Fito. Mientras menos guardias sean utilizados, más puntos se obtienen al final. En este caso Fito solo quiere maximizar los puntos, por lo que no le importa gastar todos los diamantes, o escoger una ruta más larga. Ayuda a Fito diciéndole la menor cantidad de soldados que se necesita para completar el nivel.

La primera línea de la entrada contiene cuatro enteros separados por un espacio: $n$ $(1 \leq n \leq 100)$ que indica la cantidad de ciudades, $m$ $ (1 \leq m \leq 10^{4})$ la cantidad de caminos y $s,t$ $(1 \leq s, t \leq n)$ las ciudades de salida y llegada respectivamente. En la segunda línea aparecen dos enteros $D$ $(0 \leq D \leq 10^{6})$ y $T$ $(0 \leq T \leq 10^{6} )$ separados por un espacio, que representan respectivamente la cantidad inicial de diamantes y el tiempo para completar el nivel. En las siguientes $m$ líneas se describen los caminos entre las ciudades. En cada línea aparecen cinco enteros $u,v,c_{i},t_{i}$ y $g_{i}$ separados por un espacio e indicando que hay un camino desde la ciudad $u$ a la $v$ $(1\leq u,v \leq n)$, con tiempo necesario $t_i$ $(0 \leq t_i \leq 10^{4})$, requiriendo una cantidad de guardias igual a $g_i$ $(0 \leq g_i \leq 10^{6})$ y exigiendo por su uso $c_{i} \in \left\{0,1 \right\}$ diamantes.

La salida debe ser un entero con la menor cantidad de guardias necesarios para transportar el tesoro sin riesgos, respetando las condiciones del nivel. En caso de que no sea posible se debe imprimir -1.