Examination

Time limit: 1 seconds

Memory limit: 512 megabytes

Problem Statement

There are many problems in the math exam of PKU winter camp. All the problems are divided into $n$ groups. In the $i$-th $(1 \leq i\leq n)$ group there are $p_i$ problems, you can get $s_i$ points by solving each of them and $c_i$ bonus points by solving all the problems in this group.

You are going to take part in the PKU winter camp and you want to know how many problems you need to solve at least to get $d$ points?

Input

The first line contains two integers $n, d(2\leq n\leq 100,1\leq d \leq 10^4)$ denoting the groups of the exam and the $d$ points you want to get at least.

In the following $n$ lines, each line contains three integers $p_i,s_i,c_i(2\leq p_i\leq 100,1\leq c_i\leq 1000,1\leq s_i\leq 100)$ denoting there are $p_i$ problems in the $i$-th group, the basic points of each problem $s_i$ and the bonus points $c_i$ of solving all the problems in this group.

Output

Print a single integer, denoting the answer to the question.

2 7
3 1 5
5 2 8

3

Notes

One possible solution: solve all the problems of the first group, and you can get $1 * 3 + 5 = 8$ points.