The Timetable from "Diez-Product"#64
After computerizing the educational institution and installing computers in every classroom, the director and deputy director realized that they could not do without the "Timetable" program from the "Diez-Product" company.
There are classrooms in the institution, and lessons must be conducted. The complication is that the equipment differs in every classroom, so the duration of lessons in each room is different. According to safety and hygiene standards, each classroom has a cleaning schedule: after a certain number of lessons, a technical break of a specific duration must be taken. Both this interval and the break duration may differ between classrooms (as the sizes and staff are different).
Help the administration determine the minimal total time required to conduct all the planned lessons.
The first line contains two integers: the number of classrooms and the number of lessons . Each of the following lines contains three integers: the duration of one lesson in the -th classroom U_i, the number of lessons C_i after which a technical break must be held, and the duration of the break T_i.
1 \leq N \leq 50, 1 \leq K \leq 2000, 30 \leq U_i \leq 120, 1 \leq C_i \leq 100, 10 \leq T_i \leq 50.
Output a single integer — the minimal total time required to conduct all lessons.
Example 1