Planificación óptima (2) P96822

Se tiene n tareas a realizar, cada una de las cuales requiere un cierto número de minutos ‍t_i. Para cada tarea i, se conoce el minuto máximo f_i en el cual i debe estar finalizada. Además, realizar cada tarea i tiene valor v_i. Si sólo se dispone del intervalo de tiempo desde el instante 0 hasta el minuto m, ¿cuál es el máximo valor total de las tareas que se pueden realizar respetando las restricciones?

Entrada

La entrada consiste en diversos casos. Cada caso empieza con n y m, seguidas de n triplas con t_i, f_i y v_i. Podéis suponer 1 ≤ n ≤ 100, m ≥ 1, 1 ≤ t_i ≤ f_i y v_i ≥ 1.

Salida

Para cada caso, escribid la máxima suma de valores de tareas realizables.

Puntuación

• test-1:  ‍ Entradas donde m ≤ 100, t_i = 1, f_i ≤ 100 y v_i = 1.  ‍10 Puntos ‍

• test-2:  ‍ Entradas donde m ≤ 10⁸, t_i = 1, f_i ≤ 10⁶ y v_i ≤ 10⁶.  ‍25 Puntos ‍

• test-3:  ‍ Entradas donde m ≤ 10⁸, f_i ≤ 10⁶ y v_i = 1.  ‍25 Puntos ‍

• test-4:  ‍ Entradas donde m ≤ 10⁸, f_i ≤ 10⁶ y v_i ≤ 10⁶.  ‍40 Puntos ‍