Stop & Go

면접 대비

시간 제한2초메모리 제한1024 MB

요약

길이 L인 도로에 신호등 N개가 있을 때, Mr. D가 지점 L에 도착하는 시각을 구합니다. 빨간불을 만나면 멈추고, 그 밖에는 속도 1로 달립니다.

난이도: 보통10점 중 4점
유형: 시뮬레이션, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

Mr. Drive, 일명 Mr. D는 항상 정확히 법정 속도로 운전한다. 교차로에 진입하는 순간 신호가 초록에서 빨강으로 바뀌면 바로 차를 세운다. 신호가 빨강에서 초록으로 바뀌면 바로 출발해서 법정 속도로 달린다.

Mr. D의 다음 주행 코스는 길이 $L$ 인 직선 도로이며, 제한 속도는 초당 1이다. Mr. D는 시각 0에 출발점에서 출발하고, 초당 1의 속도로 달린다. 도로에는 1번부터 $N$ 번까지 번호가 붙은 신호등이 $N$ 개 있다. 신호등 $i$ 는 출발점에서 $x_i$ 만큼 떨어져 있다. 시각 0에는 모든 신호등이 초록색이다. 신호등 $i$ 는 초록색이 $g_i$ 초 지속된 뒤 빨간색으로 바뀌고, 빨간색이 $r_i$ 초 지속된 뒤 다시 초록색이 된다. 이후 초록색이 다시 $g_i$ 초 지속되면 빨간색으로 바뀌고, 이 과정이 반복된다.

Mr. D가 $x_i$ 에 도달했을 때 신호등 $i$ 가 초록색이거나 빨강에서 막 초록으로 바뀐 상태라면, 멈추지 않고 초당 1의 속도로 통과한다. 신호등 $i$ 가 빨간색이거나 초록에서 막 빨강으로 바뀐 상태라면, 신호등이 초록색이 될 때까지 멈춰 있는다.

Mr. D가 점 $L$ 에 도달하는 시각을 구하라.

입력

첫 번째 줄에 정수 $N$ ( $1 \le N \le 100000$ )과 $L$ ( $1 \le L \le 10^9$ )이 주어진다. 이후 $N$ 개의 줄에는 각각 정수 $x_i$ , $g_i$ , $r_i$ ( $1 \le x_i < L$ , $1 \le g_i \le 10^9$ , $1 \le r_i \le 10^9$ )가 주어진다. 모든 $x_i$ 는 서로 다르다.

출력

Mr. D가 점 $L$ 에 도달하는 시각을 초 단위의 정수 하나로 출력한다.

예제3

예제 1
입력
```
3 10
3 2 2
6 1 1
9 2 5
```
예상 출력
```
15
```
예제 2
입력
```
1 100
50 1000 1
```
예상 출력
```
100
```
예제 3
입력
```
3 100
70 10 50
20 10 15
50 50 10
```
예상 출력
```
150
```