Se tienen ~N~ intervalos cerrados. El ~i~-ésimo intervalo cubre ~[s_i, e_i]~ y tiene un peso entero positivo ~w_i~. Considera un grafo no dirigido de ~N~ vértices, donde cada vértice corresponde a un intervalo, y entre dos vértices existe una arista si y solo si los dos intervalos correspondientes tienen una intersección no vacía. Para una lista de grafos, llamamos este grafo el grafo de intervalos.

Pepe quiere que el grafo no tenga ninguna componente mayor que ~K~. Para cumplir eso, él puede eliminar cero o más intervalos. Pepe es vago, así que de todas las vías posibles de eliminar intervalos, seleccionará la que minimice el peso total de los intervalos que deberá eliminar.

Imprime el peso total de los intervalos que deberá eliminar Pepe para que todas las componentes del grafo de intervalos tengan tamaño menor o igual a ~K~.

Entrada

La primera línea contiene dos enteros ~N~ y ~K~ (~1 \le K \le N \le 2\,500~).

Cada una de las siguientes ~N~ líneas contiene tres enteros ~s_i, e_i, w_i~ (~1 \le s_i \le e_i \le 10^9~, ~1 \le w_i \le 10^{9}~).

Salida

Imprime la suma de los pesos de los intervalos eliminados por Pepe.

Subtareas

• Subtarea 1: ~s_i = e_i~ y ~w_i = 1~ para todos los intervalos (9 puntos)
• Subtarea 2: ~s_i = e_i~ para todos los intervalos (9 puntos)
• Subtarea 3: ~w_i = 1~ para todos los intervalos, ~k = 1~ (11 puntos)
• Subtarea 4: ~k = 1~ (14 puntos)
• Subtarea 5: ~n \leq 100~ (30 puntos)
• Subtarea 6: Sin restricciones adicionales (27 puntos)

Ejemplo de entrada

5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1

Ejemplo de salida

3

Nota del ejemplo

Una posible solución es eliminar el segundo intervalo y el quinto.