27278번 - 영내순환버스

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

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

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

병사들은 버스를 기다리기 시작한 시각부터 버스가 자신의 승차 지점에 도착하는 즉시 탑승하며, 그 후 버스가 자신의 하차 지점에 도착하는 즉시 하차한다.

오늘도 $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$번째 줄까지 $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)$

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