#P2022F. Examination

    ID: 117 Type: Default 1000ms 256MiB Tried: 33 Accepted: 5 Difficulty: 8 Uploaded By: Tags>福建师范大学第19届程序设计竞赛

Examination

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 nn groups. In the ii-th (1in)(1 \leq i\leq n) group there are pip_i problems, you can get sis_i points by solving each of them and cic_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 dd points?

Input

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

In the following nn 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 pip_i problems in the ii-th group, the basic points of each problem sis_i and the bonus points cic_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 13+5=81 * 3 + 5 = 8 points.