FA수의 진

면접 대비

시간 제한1초메모리 제한512 MB

요약

각 횡단보도에서 신호를 기다려 건널지 육교를 이용할지 정해, 0구역에서 N구역까지 가는 최소 시간을 구합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

서강대학교에는 하나의 강의를 $5$ 번 결석하면 F 학점을 주는 FA 제도가 있다. 근수는 알고리즘 설계와 분석 강의를 이미 4번 결석한 상태이고, 한 번 더 결석하면 F 학점을 받는다. 강의실까지의 거리는 그리 멀지 않지만, 가는 길에 있는 횡단보도가 발목을 잡는다.

얼마 전 학교는 횡단보도 때문에 지각하는 학생이 없도록 모든 횡단보도 옆에 육교를 설치했다. 육교를 이용하면 신호를 기다리지 않고 도로를 건널 수는 있지만, 이동 거리가 달라져서 시간이 더 걸릴 수도 있다. 근수는 신호를 기다릴지 육교를 건널지 판단해서 최대한 빨리 학교에 도달하려고 한다.

근수는 일렬로 이어진 $N$ 개의 횡단보도를 전부 지나야 학교에 도착한다. 편의상 $N$ 개의 횡단보도로 나뉜 $N+1$ 개의 구역에 $0$ 부터 $N$ 까지 번호를 붙인다. $i-1$ 번 구역과 $i$ 번 구역 사이의 횡단보도를 $i$ 번째 횡단보도라고 부른다. 근수는 $0$ 번 구역에 있고, 강의실은 $N$ 번 구역에 있다.

근수는 횡단보도마다 다음 네 가지 값을 정리했다.

$A_i$ : $i-1$ 번 구역에서 $i$ 번 구역으로 횡단보도를 이용해 이동하는 데 걸리는 시간이다.
$B_i$ : $i-1$ 번 구역에서 $i$ 번 구역으로 육교를 이용해 이동하는 데 걸리는 시간이다.
$C_i$ : $i$ 번째 신호등이 녹색으로 유지되는 시간(분)이다. 녹색이 된 뒤 정확히 $C_i$ 분이 지나면 적색으로 바뀐다.
$D_i$ : $i$ 번째 신호등이 적색으로 유지되는 시간(분)이다. 적색이 된 뒤 정확히 $D_i$ 분이 지나면 녹색으로 바뀐다.

$A_i$ 는 $i$ 번째 횡단보도를 건너는 데 걸리는 시간이 아니라, 횡단보도를 이용해 구역을 옮길 때 걸리는 시간이다. 횡단보도를 건너는 데는 1분도 걸리지 않는다. 예를 들어 신호등이 $s$ 분부터 $e$ 분까지 녹색이라고 하자. 근수가 정확히 $e$ 분에 도착하면 신호는 이미 적색이므로 건너지 못한다. $s$ 분부터 $e-1$ 분 사이에 도착하면 바로 건널 수 있다.

근수는 첫 번째 횡단보도 앞에 서 있고, 모든 신호등이 방금 동시에 녹색이 되었다고 하자. 근수가 강의실에 도달하는 데 걸리는 최소 시간을 구하라.

입력

첫 번째 줄에 횡단보도의 수를 나타내는 정수 $N$ 이 주어진다. $(1\le N \le 100\,000)$

두 번째 줄부터 $N+1$ 번째 줄까지 각 줄에 정수 $A_i$ , $B_i$ , $C_i$ , $D_i$ 가 공백으로 구분되어 주어진다. $(1 \le A_i < B_i \le 100; 1 \le C_i, D_i \le 100)$

출력

첫 번째 줄에 근수가 강의실에 도달하는 데 걸리는 최소 시간 $x$ 분을 출력한다. $x$ 는 항상 음이 아닌 정수이다.

예제2

예제 1
입력
```
3
2 3 1 1
1 2 2 4
1 2 2 2
```
예상 출력
```
5
```
예제 2
입력
```
3
3 4 1 1
2 100 2 2
1 2 6 6
```
예상 출력
```
8
```