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 \le n \le 100$, $m \ge 1$, $1 \le t_i \le f_i$ y $v_i \ge 1$.

Salida

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

Puntuación

• test-1:   Entradas donde $m \le 100$, $t_i = 1$, $f_i \le 100$ y $v_i = 1$.

• test-2:   Entradas donde $m \le 10^8$, $t_i = 1$, $f_i \le 10^6$ y $v_i \le 10^6$.

• test-3:   Entradas donde $m \le 10^8$, $f_i \le 10^6$ y $v_i = 1$.

• test-4:   Entradas donde $m \le 10^8$, $f_i \le 10^6$ y $v_i \le 10^6$.