참살이길

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

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

참살이길은 시작점의 좌표가 0이고 끝점의 좌표가 $n$인 수직선으로 볼 수 있다. 신호등은 정수 좌표에만 놓일 수 있다. 각 신호등은 빨간 불과 초록 불이 번갈아 켜진다. $i$번째 신호등은 빨간 불이 $t_i$초 동안 켜졌다가 초록 불이 $t_i$초 동안 켜지고, 이를 반복한다. 이 신호등은 윤헌이가 주행을 시작한 뒤 $s_i$초가 지나면 처음으로 빨간 불에서 초록 불로 바뀐다. 차는 빨간 불인 동안 신호등 위치에 반드시 멈춰야 하고, 초록 불인 동안에는 문제없이 지나갈 수 있다.

차는 1 m/s로 움직인다. 가속이나 감속은 없으며, 이 속도로 움직이거나 멈춘다. 시작점과 끝점에는 신호등이 없고, 같은 정수 좌표에 신호등이 두 개 이상 놓이지 않는다. 신호등이 초록 불에서 빨간 불로 바뀌는 순간에 차가 그 위치에 있으면, 차는 출발할 수 없다.

첫째 줄에 참살이길의 길이 $n$과 신호등의 개수 $k$가 공백으로 구분되어 주어진다.

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

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

• $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$)
• 한 정수 좌표점에 두 개 이상의 신호등이 존재할 수 없다.

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