영내순환버스

영내에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 승하차 지점이 있다. 화창한 아침, 운전병은 오늘도 병사들의 영내 이동을 돕기 위해 버스의 시동을 걸었다.

운전병의 버스는 영내순환버스라 불리며, 다음과 같은 특징이 있다.

• 영내순환버스는 시각 $0$에 $1$번 지점에서 출발하여 $2$번, $3$번, $\cdots$, $N$번 지점을 순서대로 방문한 뒤 다시 $1$번 지점으로 돌아온다. 이 경로를 계속 순환한다.
• 버스가 출발한 후에는 $M$명의 병사가 모두 탑승하고 하차할 때까지 멈출 수 없다.
• 버스의 수용 인원에는 제한이 없다. 즉, 승차하려는 병사는 언제나 탈 수 있다.

병사는 버스를 기다리기 시작한 시각부터 버스가 자신의 승차 지점에 도착하는 즉시 탑승한다. 이후 버스가 자신의 하차 지점에 도착하는 즉시 내린다.

운전병은 마지막 병사가 하차하자마자 운전 업무를 마쳤다. 운전병이 운전 업무를 마친 시각을 구하여라.

첫 번째 줄에 승하차 지점 수 $N$과 병사 수 $M$이 공백으로 구분되어 주어진다. $(2 \leq N \leq 100\,000;$ $1 \leq M \leq 100\,000)$

두 번째 줄에 $i$번 지점에서 $i+1$번 지점으로 갈 때 걸리는 시간 $t_i$가 공백으로 구분되어 정수로 주어진다. 단, $t_N$은 $N$번 지점에서 $1$번 지점으로 되돌아갈 때 걸리는 시간이다. $(1 \leq i \leq N;$ $1 \leq t_i \leq 1\,000)$

세 번째 줄부터 $2+M$번째 줄까지 각 줄에 병사 한 명의 승차 지점 $p_i$, 하차 지점 $r_i$, 승차 지점에서 버스를 기다리기 시작한 시각 $c_i$가 공백으로 구분되어 정수로 주어진다. $(1 \leq i \leq M;$ $1 \leq p_i, r_i \leq N;$ $p_i \neq r_i;$ $0 \leq c_i \leq 10^9)$

첫 번째 줄에 운전병이 운전 업무를 마친 시각을 출력한다.