Ralph decided to give Vanellope one very beautiful model car for her birthday and now is looking for where to buy it. Ralph found n stores that sell this model and numbered them from 1 to n. In the shop number i, the model costs pi points.

Since Ralph is always very busy, he does not have time to go to the store. Therefore, he decided to use the delivery service, which is available in all stores. In shop number i, shipping costs di points. A feature of local deliveries is that the gasoline that the driver of the car spends is always paid separately. Ralph knows that gas now costs c points per liter, and he also knows that the delivery truck will use exactly vi liters of gasoline to get to the store with number i.

Help Ralph to determine the minimum cost of the desired model, including shipping, among all the stores he found.

Input

The first line contains two integers n and c (1 ≤ n, c ≤ 100) - the number of stores found by Ralph and the cost gasoline per liter, respectively.

Each of the following n lines contains three integers pi, di, vi (1 ≤ pi, di, vi ≤ 100) - the cost of the model, the cost of delivery and the volume of gasoline in liters required for delivery for the store with the number i.

Output

Print a single integer - the minimum cost of the model including shipping.