Delivery

Time limit2sMemory limit1024 MB

Summary

Each shop costs p plus d plus C times v, and the task is to output the smallest such total over all n shops.

Level: Easy1 of 10
Topics: Implementation, Brute force
Solved: No attempts yet

Problem

Ralph wants to buy a very pretty model car as a birthday gift for Vanellope. He found $n$ shops that sell this model and numbered them from 1 to $n$ . In shop $i$ , the model costs $p_i$ points.

Ralph is always busy and has no time to drive to a shop, so he plans to use the delivery service that every shop offers. The delivery fee in shop $i$ is $d_i$ points. Fuel for the delivery vehicle is paid separately. Gasoline currently costs $C$ points per liter, and the delivery vehicle from shop $i$ uses exactly $v_i$ liters to reach Ralph.

Help Ralph find the minimum cost of the model including delivery, over all the shops he found.

Input

The first line contains two integers $n$ and $C$ , the number of shops and the price of gasoline per liter ( $1 \le n, C \le 100$ ).

Each of the next $n$ lines contains three integers $p_i$ , $d_i$ , and $v_i$ : the price of the model, the delivery fee, and the liters of gasoline needed for delivery at shop $i$ ( $1 \le p_i, d_i, v_i \le 100$ ).

Output

Print one integer, the minimum cost of the model including delivery.

Examples1

Example 1
Input
```
3 2
1 1 3
3 2 1
5 1 1
```
Expected output
```
7
```