Matcom Online Grader

Fito ha entrado en un concurso un poco diferente. El concurso consiste en hacer muñecos de nieve. Hasta ahí no hay problemas porque Fito es muy bueno en esta tarea, sin embargo en este caso no vale cualquier figura. Antes de empezar el concurso los jueces reparten unas fotos con los posibles muñecos y cualquier otro no aporta puntos. Ellos también especifican el tiempo en segundos que durará el concurso, dejando claro que solo los muñecos que se hagan antes de ese tiempo suman puntos, aunque si se termino uno justo en el segundo final sí cuenta. No contento con las restricciones usuales, este año los jueces han puesto una regla nueva porque las temperaturas han sido relativamente altas y la nieve se ha ido descongelando a lo largo del día. La regla consiste en descontar puntos a la figura basada en la cantidad de nieve derretida. Fito tiene mucha experiencia haciendo muñecos de nieve y sabe exactamente cuánto tiempo se demora en hacer cada uno, además sabe la cantidad de puntos que va perdiendo un muñeco cada segundo. Esto último lo sabe estimando la cantidad de nieve que necesita para hacer cada muñeco y por tanto la cantidad que se va a ir derritiendo con el tiempo. Como Fito desea ganar él quiere saber qué muñecos hacer y en qué orden y para esto sabe cuántos puntos vale cada figura, cuánto tiempo se demora en hacerla y la cantidad de puntos que va perdiendo con el tiempo.

La primera línea de la entrada contiene dos enteros separados por un espacio $N$ y $T$ donde $N$ ($1 \leq N \leq 50$) es la cantidad de muñecos que Fito puede hacer y $T$ ($1 \leq T \leq 100000$) es el tiempo total en segundos que dura el concurso. Después le siguen $N$ líneas cada una con tres enteros separados por un espacio. Cada línea describe un posible muñeco de nieve con tres valores: $C_i$ ($1 \leq Ci \leq 100000$), $D_i$ ($1 \leq D_i \leq 100000$) y $T_i$ ($1 \leq T_i \leq 100000$) que representan la ganancia inicial, la cantidad de puntos que pierde por segundo y el tiempo en segundos que es necesario para hacerlo respectivamente.