Yongsik Goes to Camp

Interview

Time limit2sMemory limit128 MB

Summary

For N bus schedules given by first departure, interval, and count, find the minimum wait until Yongsik can board any bus after arriving at time T, or -1 if none is available.

Level: Easy3 of 10
Topics: Simulation, Math, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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}$ .

Constraints

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

Hint

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.

Examples5

Example 1
Input
```
1 285
150 50 10
```
Expected output
```
15
```
Example 2
Input
```
1 123456
123456 10000 1
```
Expected output
```
0
```

Example 3

Input

3 1
270758 196 67
904526 8930 66
121164 3160 56

Expected output

Example 4

Input

3 1000000
718571 2557 74
480573 9706 54
16511 6660 90

Expected output

-1

Example 5

Input

5 395439
407917 8774 24
331425 4386 58
502205 9420 32
591461 1548 79
504695 8047 53

Expected output