| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 392 | 173 | 138 | 46.465% |
영내에는 1ドル$번부터 $N$번까지 번호가 매겨져 있는 $N$개의 승하차 지점이 있다. 화창한 아침, 운전병은 오늘도 병사들의 영내 이동을 지원하기 위해 버스의 시동을 걸었다.
운전병의 버스는 영내순환버스라 불리며, 다음과 같은 특징을 지닌다.
병사들은 버스를 기다리기 시작한 시각부터 버스가 자신의 승차 지점에 도착하는 즉시 탑승하며, 그 후 버스가 자신의 하차 지점에 도착하는 즉시 하차한다.
오늘도 $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)$
첫 번째 줄에 운전병이 운전 업무를 마친 시각을 출력한다.
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
26
입력에서 주어진 순서대로 각각 1ドル$번 병사부터 7ドル$번 병사라고 할 때, 각 병사의 버스 탑승 시각 및 하차 시각은 다음과 같다.
Contest > 보라매컵 > 제1회 보라매컵 본선 B번