Problem Description

　　大赛将至，摆在你面前的是n道题目，第i(1≤i≤n) 道题目能提升a​i​​ 点智力值，代码量为b​i​​ KB，无聊值为c​i。

　　求至少提升m点智力值的情况下，所做题目代码量之和*无聊值之和最小为多少。

　　样例解释：

　　选择第1、3、4道题

Input

　　多组测试数据

　　第一行两个整数n,m(0<n≤400) 接下来nn行每行三个数，a​i​​, b​i​​, c​i​​(0<b​i​​,c​i​​≤1000,0<a​i​​≤800)。 0 < m ≤ ∑a​i ​​≤ 800

Output

　　一个数，至少提升mm点智力值的情况下，所做题目代码量之和*∗无聊值之和的最小值。

Sample Input

4 63 7 22 2 41 3 32 5 1

Sample Output

90