25920번 - Yonsei Formula 1

연세대학교 레이싱 팀은 대회에 참가했다. 대회를 완주하기 위해서는 트랙을 $M$바퀴 돌아야 한다. 트랙은 둘레의 길이가 $L$인 원이다. 트랙에는 시작 지점이 존재하고 시작 지점에서 출발해 $L$만큼 주행하면 한 바퀴를 돈 것으로 인정된다. 트랙은 원형이므로 시작 지점에서 $L$만큼 주행하면 다시 시작 지점에 도착하게 된다.

레이싱카가 움직이기 위해서는 반드시 시작 지점에서 타이어를 장착한 후 주행해야 한다. 연세대학교 레이싱 팀은 $N$개의 타이어를 준비해 왔고 오직 순서대로만 교체할 수 있다. $i$번째 타이어로 교체하자마자 $i+1$번째 타이어로 교체하는 것도 가능하다. 그러나 $N$번째 타이어로 교체한 이후에는 더 이상 교체할 수 있는 타이어가 없으므로 더 이상 교체할 수 없다.

타이어는 매 분마다 성능이 있다. $t$분에 어떤 타이어의 성능이 $v$라면 $t+1$분까지 현재 위치에서 최대 $v$만큼 주행할 수 있다. 즉, $t$분의 레이싱카의 위치가 $x$라면 $t+1$분에는 $[x,x+v]$에 위치할 수 있다. 그러나 어떤 위치에 도착해도 $t+1$분에 도착하게 된다. 따라서 완주 및 교체는 오직 정수 시간에만 이루어질 수 있다.

타이어마다 3개의 옵션 $a_i$, $b_i$, $d_i$이 각각 주어진다. $i$번째 타이어는 교체하자마자 $a_i$의 성능을 지닌다. 이후 성능이 $b_i$에 이르기까지 매 분마다 성능이 $d_i$씩 감소한다. 따라서 $t$분의 타이어의 성능이 $v$였을때, $v=b_i$라면 $t+1$분의 성능 또한 $b_i$이고 $v > b_i$라면 $t+1$분의 성능은 $v-d_i$이다.

오직 시작 지점에서만 타이어를 교체할 수 있다. 연세대학교의 메카닉들은 매우 숙련되었기 때문에 타이어를 장착하거나 탈착하는 시간은 무시한다.

0분에 레이싱 경기가 시작한다. 맨 처음 레이싱카에는 아무런 타이어도 장착되어 있지 않다. 몇 분 만에 연세대학교 레이싱팀이 대회를 완주할 수 있는지 구해보자.

입력은 아래와 같이 주어진다.

몇 분 만에 연세대학교 레이싱 팀이 대회를 완주할 수 있는지 출력한다.

• $1 \leq N \leq 1\,000$
• $1 \leq M \leq 100$
• $1 \leq L \leq 10^9$
• $1 \leq b_i \leq a_i \leq 10^9$
• $1 \leq d_i \leq 10^9$
• $a_i - b_i$는 $d_i$의 배수이다.