Bessie es una vaca muy trabajadora. De hecho, ella está tan enfocada en maximizar su productividad que ella decide planificar sus siguientes ~N (1 \leq N \leq 1,000,000)~ horas (convenientemente rotuladas ~0..N-1~) de tal manera que ella produzca tanta leche como sea posible.

El Granjero Juan tiene una lista de ~M (1 \leq M \leq 1,000)~ intervalos posiblemente sobrelapados en los cuales él está disponible para ordeño. Cada intervalo i tiene una hora inicial ~(0 \leq horainicial_i < N)~, y hora de finalización ~(horaincial_i < horafinal_i \leq N)~, y una eficiencia correspondiente ~(1 \leq eficiencia_i \leq 1,000,000)~ la cual indica cuántos galones de leche él puede obtener de Bessie en ese intervalo. El Granejro Juan comienza y termina a ordeñar al comienzo de la hora inicial y al final de la hora final, respectivamente. Cuando es ordeñada, Bessie debe ser ordeñada durante un intervalo completo.

Sin embargo, aún Bessie tiene sus limitaciones. Después de ser ordeñada durante cualquier intervalo, ella debe descansar ~R (1 \leq R \leq N)~ horas antes de comenzar a ser ordeñada nuevamente. Dada la lista de intervalos del Granjero Juan, determine la máxima cantidad de leche que Bessie puede producir en las ~N~ horas.

Entrada

• Línea 1: Tres enteros separados por espacios: ~N, M,~ y ~R~.

• Líneas 2..M+1: La línea i+1 describe el intervalo iésimo de GJ con tres enteros separados por espacios: ~horainicial_i, horafinal_i~, y ~eficiencia_i~.

Ejemplo de Entrada

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

Detalles de la Entrada

Bessie quiere planificar las siguientes 12 horas; el Granjero Juan tiene 4 intervalos no sobrelapados en los cuales él puede ordeñarla; Bessie debe descansar 2 horas después de cada ordeñada. El primer intervalo va de la hora 1 a la hora 2, el segundo de la hora 10 a la hora 12, el tercero de la hora 3 a la hora 6, y el cuarto de la hora 7 a la hora 10. El Granjero Juan puede obtener 8, 19, 24, y 31 galones de leche, respectivamente, de Bessie en esos intervalos.

Salida

• Línea 1: El máximo número de galones de leche que Bessie puede producir en las ~N~ horas

Ejemplo de Salida

43

Detalles de la Salida>:

Si Bessie usa el primer intervalo, ella no puede usar el tercero debido a que necesita 2 horas de descanso. Si usa el segundo, ella no puede usar el cuarto. Finalmente, si ella usa el tercero, ella no puede usar el cuarto. La mejor situación es elegir los intervalos segundo y tercero, produciendo 43 galones de leche.