cho.sh영내순환버스
아직 제출이 없습니다시간 제한1초메모리 제한1024 MB문제 설명
예제1
문제
영내에는 1번부터 N번까지 번호가 매겨져 있는 N개의 승하차 지점이 있다. 화창한 아침, 운전병은 오늘도 병사들의 영내 이동을 지원하기 위해 버스의 시동을 걸었다.
운전병의 버스는 영내순환버스라 불리며, 다음과 같은 특징을 지닌다.
- 영내순환버스는 시각 0에 1번 지점에서 출발하여 순서대로 2번, 3번, ⋯, N번 지점까지 방문한 후 다시 1번 지점으로 돌아오며, 이 경로를 계속 순환한다.
- 버스가 출발한 후에는 M명의 병사가 모두 버스를 이용하고 하차하기 전까지 멈출 수 없다.
- 버스의 수용 인원에 제한이 없다. 즉, 버스에 승차하려는 병사는 항상 탑승할 수 있다.
병사들은 버스를 기다리기 시작한 시각부터 버스가 자신의 승차 지점에 도착하는 즉시 탑승하며, 그 후 버스가 자신의 하차 지점에 도착하는 즉시 하차한다.
오늘도 M명의 모든 병사의 영내 이동을 지원한 운전병은 마지막 병사가 하차하자마자 운전 업무를 마쳤다. 운전병이 운전 업무를 마친 시각을 구하여라.
입력
첫 번째 줄에 승하차 지점 수 N과 병사 수 M이 공백으로 구분되어 주어진다. (2≤N≤100,000; 1≤M≤100,000)
두 번째 줄에 i번 지점에서 i+1번 지점으로 갈 때 걸리는 시간 t_i가 공백으로 구분되어 정수로 주어진다. 단, t_N은 N번 지점에서 1번 지점으로 되돌아갈 때 걸리는 시간이다. (1≤i≤N; 1≤t_i≤1,000)
세 번째 줄부터 2+M번째 줄까지 M명의 병사에 대하여, 각 줄에 병사의 승차 지점 p_i, 하차 지점 r_i, 승차 지점에서 버스를 기다리기 시작한 시각 c_i가 공백으로 구분되어 정수로 주어진다. (1≤i≤M; 1≤p_i,r_i≤N; p_i=r_i; 0≤c_i≤109)
출력
첫 번째 줄에 운전병이 운전 업무를 마친 시각을 출력한다.