Imaginándose que ellas no pueden hacerlo peor que los humanos, las vacas del Granjero Juan han decidido abrir una aerolínea. Siendo vacas, ellas deciden abastecer el mercado no explotado de vacas como pasajeras. Ellas planean servir a las vacas que viven a lo largo de la costa oeste del Lago Moochigan. Cada mañana, ellas volarán desde el punto más al norte de la costa hacia el sur hacia Chicago, haciendo muchas paradas a través del camino. Cada tarde, ellas volarán de regreso hacia el norte hacia el punto más al norte.

Ellas necesitan que usted les ayude a decidir cuales pasajeras llevar cada día. Cada una de las ~N~ granjas numeradas ~1..N~ a través de la costa contiene un aeropuerto (La Granja 1 es la granja más al norte; la granja ~N~ es la más al Sur). En este día, ~K~ grupos de vacas desean viajar. Cada grupo quiere viajar de una granja en particular a otra granja en particular. A la aerolínea, si quiere, se le permite parar y recoger solo una parte de un grupo. Las vacas que comienzan un viaje, sin embargo, deben permanecer en el avión hasta que ellas lleguen a su destino.

Dada la capacidad ~C~ del aeroplano y los grupos de vacas que necesitan viajar, determine el máximo número de vacas que la aerolínea puede llevar a su destino.

Entrada

• Línea 1: Tres enteros separados por espacios: ~K, N,~ y ~C~.
• Líneas 2..K+1: Cada línea contiene tres enteros sepados por espacios ~S, E~ y ~M~ que especifican un grupo de vacas que quiere viajar. Las ~M~ vacas están actualmente en la granja ~S~ y quieren viajar a la granja ~E~ ~(S \neq E)~.

Salida

El máximo número de vacas que pueden volar a su destino. Esto es la suma del número de vacas que volaron a su destino en los viajes que salieron hacia el sur en la mañana mas el número de vacas que volaron a su destino en el viaje hacia el norte en la tarde.

Restricciones

• ~1 \leq N \leq 10,000~
• ~1 \leq K \leq 50,000~
• ~1 \leq C \leq 100~
• ~1 \leq M \leq C~

Ejemplo de Entrada

4 8 3
1 3 2
2 8 3
4 7 1
8 3 2

Destalles de la Entrada: Cuatro grupos de vacas, ocho granjas y tres asientos en el avión.

Ejemplo de Salida

6

Destalles de la Salida: En la mañana, el vuelo toma 2 vacas de ~1->3~, 1 vaca de ~2->8~ y una vaca de ~4->7~. En la tarde, el vuelo toma 2 vacas de ~8->3~.