27376번 - 참살이길

문제

윤헌이는 현대모비스의 협찬을 받아 MOBIS X라는 자율주행차를 갖게 되었다. 사고율 0%를 자랑한다는 이 자율주행차의 성능이 너무 궁금했던 윤헌이는 당장 참살이길로 나가 시운전을 해 보기로 마음먹었다.

참살이길은 전체 길이가 $n$ 미터이고, 그 위에 $k$개의 신호등이 존재한다. 윤헌이는 참살이길의 시작점에서 끝점까지 도달하는 데 얼마나 시간이 걸리는지 알고 싶다.

참살이길은 시작점 좌표가 0ドル$이고 끝점 좌표가 $n$인 수직선으로 가정할 수 있고, 신호등은 오직 정수 좌표점에만 존재할 수 있다. 신호등은 빨간 불과 초록 불 두 가지 상태를 갖고 있으며, $i$번째 신호등은 빨간 불과 초록 불이 각각 $t_i$초 동안 번갈아가면서 켜진다. 또한, 윤헌이가 주행을 시작한 시점에서 $s_i$초 이후에 이 신호등은 처음으로 빨간 불에서 초록 불이 된다. 빨간 불일 때 차는 신호등 위치에서 반드시 정지해야만 하며, 초록 불일 때는 문제 없이 지나갈 수 있다.

참살이길에서는 과속하면 안 되기 때문에 MOBIS X는 1ドルm/s$의 속도로 이동하며, 가속이나 감속 없이 항상 이 속도로 이동하거나 아니면 정지한다. 시작점과 끝점에는 신호등이 존재하지 않으며, 한 정수 좌표점에 두 개 이상의 신호등이 존재할 수 없다. 또한 신호등이 초록 불에서 빨간 불로 바뀌는 시점에 해당 신호등 위치에 있는 차는 출발할 수 없다.

각 신호등의 좌표 $x$와 주기 $t$가 주어질 때, 윤헌이가 참살이길을 가장 빠르게 완주하는 데 걸리는 시간을 알아보자!

입력

참살이길의 길이와 신호등의 개수를 나타내는 두 정수 $n,ドル $k$가 공백으로 구분되어 주어진다.

다음 $k$개의 줄 중 $i$번째 줄에 $i$번째 신호등의 좌표와 주기, 그리고 윤헌이가 출발한 이후 처음으로 이 신호등이 초록 불이 될 때까지 걸린 시간을 나타내는 세 정수 $x_i, t_i, s_i$가 공백으로 구분되어 주어진다. (1ドル \le i \le k$)

출력

윤헌이가 참살이길을 완주하는 데 걸리는 시간을 초(s) 단위로 출력한다.

제한

• 1ドル \le n \le 10^9$
• 0ドル \le k \le \min(10^5, n-1)$
• 1ドル \le x_i \le n-1$ (1ドル \le i \le k$)
• 1ドル \le t_i \le 10^9$ (1ドル \le i \le k$)
• 0ドル \le s_i \le t_i -1$ (1ドル \le i \le k$)
• 한 정수 좌표점에 두 개 이상의 신호등이 존재할 수 없다.

노트

신호등이 초록 불에서 빨간 불로 바뀌는 시점에 해당 신호등 위치에 있는 차는 출발할 수 없다.