Yongsik Goes to Camp

Yongsik was supposed to take an express bus to camp with Minsik, but Minsik left by bus without waking him.

Yongsik now goes to the bus terminal by himself. At the terminal, there are N types of buses that go to the camp. Each type is described by its first departure time, interval, and number of departures. For example, if a bus type first departs 10 minutes after the reference time, has interval 10 minutes, and runs 5 times, its departures are at 10, 20, 30, 40, and 50 minutes.

Yongsik arrives at the terminal at time T. Compute the minimum number of minutes he must wait to board a bus.

The first line contains the number of bus types N and Yongsik's arrival time T. Each of the next N lines contains three integers Si, Ii, and Ci: the first departure time, the interval between departures, and the number of departures for one bus type.

Print the minimum number of minutes Yongsik must wait. If a bus departs exactly when he arrives, the answer is 0. If there is no bus he can take to reach the camp, print -1. The answer is less than $2^{31}$.

• 1 <= N <= 50
• 1 <= T <= 1,000,000
• 1 <= Si <= 1,000,000
• 1 <= Ii <= 10,000
• 1 <= Ci <= 100

In the first public test, buses depart at 150, 200, 250, ..., and 600 minutes. Therefore, Yongsik can take the bus that departs at 300 minutes.