Hay ~n~ ciudades y ~m~ rutas por las que se pueden transportar paquetes entre ciudades. Para cada ruta, se conoce el número máximo de paquetes y el costo de cada uno.

Se desea enviar ~k~ paquetes de Syrjälä a Lehmälä. ¿Cuál es la forma más económica de hacerlo?

Entrada

La primera línea de entrada contiene tres números enteros: ~n, m~ y ~k~: el número de ciudades, rutas y paquetes. Las ciudades están numeradas del ~1~ al ~n~. La ciudad ~1~ es Syrjälä y la ciudad ~n~ es Lehmälä.

A continuación, hay ~m~ líneas que describen las rutas. Cada línea contiene cuatro números enteros: ~a, b, r~ y ~c~: existe una ruta de la ciudad ~a~ a la ciudad ~b~, se pueden transportar como máximo ~r~ paquetes por la ruta y el costo de cada paquete es ~c~.

Salida

Imprima un número entero: el costo total mínimo ó -1 si no hay soluciones.

Restricciones

• ~2 \leq n \leq 500~
• ~1 \leq m \leq 1000~
• ~1 \leq k \leq 100~
• ~1 \leq a,b \leq n~
• ~1 \leq r,c \leq 1000~

Ejemplo de Entrada

4 5 3
1 2 5 100
1 3 10 50
1 4 7 500
2 4 8 350
3 4 2 100

Ejemplo de Salida

750

Explicación: Un paquete se entrega por la ruta ~1 \rightarrow 2 \rightarrow 4~ (coste ~1 \cdot 450 = 450~) y dos paquetes se entregan por la ruta ~1 \rightarrow 3 \rightarrow 4~ (cost ~2 \cdot 150=300~).