시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB182575343.443%

문제

영내에는 $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)$

출력

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

예제 입력 1

5 7
1 3 2 4 3
1 2 0
2 5 1
3 4 2
3 1 7
5 4 10
1 4 12
4 3 4

예제 출력 1

26

입력에서 주어진 순서대로 각각 $1$번 병사부터 $7$번 병사라고 할 때, 각 병사의 버스 탑승 시각 및 하차 시각은 다음과 같다.

명부 탑승 시각 하차 시각
$1$번 병사 $0$ $1$
$2$번 병사 $1$ $10$
$3$번 병사 $4$ $6$
$4$번 병사 $17$ $26$
$5$번 병사 $10$ $19$
$6$번 병사 $13$ $19$
$7$번 병사 $6$ $17$

출처

Contest > 보라매컵 > 제1회 보라매컵 본선 B번