The Timetable from "Diez-Product"

After the computerization of schools completed, when computers were set in every cabinet, a director and his deputy from educational part understood, that can’t anything to do without the program "Timetable" from the firm "Diez-product".

There are $N$ cabinets in the school. It is needed to take $K$ lessons in every of them. The computers are different in all of cabinets – that is why it is possible to work during different time in different cabinets. There is the schedule of the necessary cleanings up during special time in every cabinet (it is different for every cabinet, so as an areas of cabinets are different, and technical workers have different age) after taking of the indicated quantity of the lessons (again, it is possibly that it is different for different cabinets) according to the requirements of technique of safety and sanitary standards.

Help please to the administration of school to found out the minimum time during which they will be able to take all the lessons which planned.

Input

There is two numbers: a quantity of cabinets $N$ and a quantity of the lessons $K$ in the first line. Absence is between them. There are duration of the taking of the lessons $U_i$ in the cabinet with number $i$, a quantity of lessons in the cabinet with number $C_i$, after that is a technical break, and its duration $T_i$ in next $N$ lines.

$1\le N\le 50$, $1\le K\le 2000$, $30\le U_i\le 120$, $1\le C_i\le 100$, $10\le T_i\le 50$.

Output

There is one number in the file. It is minimum time during what all of lessons will be taking.

Examples