시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 48 15 15 35.714%

문제

영식이는 민식이와 함게 고속버스를 타고 캠프를 가야하지만, 민식이는 영식이를 깨우지 않고 혼자 버스를 타고 캠프에 가버렸다.

영식이는 혼자 고속버스터미널까지 가서 캠프에 오려고 한다. 고속버스에는 총 N가지 종류의 버스가 있다. 모든 버스는 캠프를 하는 장소까지 운행한다. 각각의 버스는 시작, 간격, 개수의 정보를 가지고 있다. 예를 들어, 어떤 버스의 시작이 10이고, 간격은 10이고, 개수가 5이면, 이 버스는 시간이 10일 때 한 대가 출발하고, 20일 때 한 대가 또 출발하고, 30일 때 한 대가 출발하고, 40일 때 한 대가 출발하고, 50일 때 한 대가 마지막으로 출발한다는 뜻이다.

영식이는 버스터미널에 T만에 도착한다. 영식이가 버스를 타기위해 기다려야하는 최소시간을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 버스의 개수 N과 영식이가 버스터미널에 도착하는 시간 T가 주어진다. 버스의 개수는 100,000보다 작거나 같은 자연수이고, 영식이가 버스터미널에 도착하는 시간은 1,000,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각각의 버스의 정보가 공백을 사이에 두고 주어진다. 버스의 정보는 “시작 간격 개수“ 이렇게 주어지며, 각각의 개수는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 영식이가 기다려야 하는 시간을 출력한다. 만약 버스가 출발하는 시간과 영식이가 터미널에 도착하는 시간이 같으면 정답은 0이 된다. 그리고, 만약 버스가 없어서 캠프에 갈 수 없을 경우에는 -1을 출력한다.

예제 입력

1 285
150 50 10

예제 출력

15

힌트

버스는 150, 200, 250, ..., 600 이렇게 출발한다. 따라서 영식이는 285에 도착하므로 300버스를 타면 된다.

출처