때는 소기 0년, 소들은 드디어 시간 여행 기술을 개발했다. 소들은 그 기념으로 이번 해를 소기 0년이라고 부르기로 했다.

소들은 과거로 시간여행을 하면 평행세계가 생기도록 제조하여, 타임 패러독스를 해결하였다.

시간 여행을 하기 위해서는 타임머신을 타야하며, 지정된 공항에서만 타고 내려야만 한다. 공항은 총 N개가 있으며 1~N까지 번호가 부여되어 있다.

또한 타임머신 운행편이 M개가 있으며 1~M개의 번호가 부여되어 있다. (1 ≤ N,M ≤ 200000)

j번 운행편은 출발 공항 c_j, 출발 년도 r_j, 도착 공항 d_j, 도착 년도 s_j (0 ≤ r_j,s_j ≤ 10⁹, s_j < r_j 가능) 4개의 정보로 이루어져 있다.

소들은 타임머신에서 내린 다음 곧바로 타임머신을 탈 수 없고, 최소한의 휴식이 필요하다. 휴식 시간은 도착 공항마다 다르다.

즉, i번 공항은 a_i년을 쉬어야 한다. (1 ≤ a_i ≤ 10⁹)

따라서, i번 공항에 s년에 도착했다면, r년에 떠나는 다른 운행편을 타기 위해서는 r ≥ s+a_i 를 만족해야 한다.

소기 0년, 소가 1번 도시에서 타임머신을 타려고 한다.

1 ~ N번 공항에 도착하는 가장 빠른 년도를 구하라.

소기 0년 (Moo Route II) timer 4s memory 32MB

소기 0년 (Moo Route II) 4s 32MB