该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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.