FA수의 진

서강대학교에는 하나의 강의를 $5$번 결석하면 F 학점을 주는 FA 제도가 있다. 현재 근수는 알고리즘 설계와 분석 강의에 4회 결석 상태인데 또다시 결석할 위기에 처해있다. 지금 있는 곳에서 강의실까지는 거리만 따지면 그렇게 멀지 않지만, 가는 길에 있는 횡단보도들이 방해된다.

얼마 전 학교에서 횡단보도 때문에 지각하는 억울한 학생들을 줄이기 위해 모든 횡단보도 옆에 육교를 설치해 두었다. 육교를 사용하면 신호등을 기다리지 않고 도로를 건널 수는 있지만 이동하는 거리가 변해서 시간이 더 걸릴 수도 있다. 그래서 근수는 신호를 기다릴지 육교를 건널지 잘 판단해 최대한 빨리 학교에 도달하고자 한다.

근수는 일렬로 이어진 $N$개의 횡단보도를 전부 지나가야 학교에 도달할 수 있다. 편의상 $N$개의 횡단보도에 의해 나눠지는 $N+1$개의 구역에 $0$부터 $N$까지 번호를 붙이기로 한다. 또, $i-1$번 구역과 $i$번 구역 사이의 횡단보도를 $i$번째 횡단보도라고 부르기로 한다. 이때 $0$번 구역에 근수가 있고, $N$번 구역에 강의실이 있다.

근수는 그동안의 경험을 토대로 횡단보도마다 $A_i$, $B_i$, $C_i$, $D_i$의 $4$가지 데이터를 정리했다. 각각의 데이터가 의미하는 바는 다음과 같다.

• $A_i$: $i-1$번 구역에서 $i$번 구역으로 이동할 때 횡단보도를 이용할 경우 걸리는 시간이다.
• $B_i$: $i-1$번 구역에서 $i$번 구역으로 이동할 때 육교를 이용하는 경우 걸리는 시간이다.
• $C_i$: $i$번째 횡단보도의 신호등이 녹색인 시간을 의미한다. $i$번째 신호등은 정확히 $C_i$분 동안 녹색을 유지한 후에 항상 적색으로 바뀐다.
• $D_i$: $i$번째 횡단보도의 신호등이 적색인 시간을 의미한다. $i$번째 신호등은 정확히 $D_i$분 동안 적색을 유지한 후에 항상 녹색으로 바뀐다.

여기서 $A_i$는 $i$번째 횡단보도를 건너는 데 걸리는 시간이 아니라 횡단보도를 이용하여 구역을 이동할 때 걸리는 시간임에 주의한다. 실제로 근수가 각각의 횡단보도를 건너는 데는 $1$분도 걸리지 않는다. 예를 들어 한 신호등이 $s$분부터 $e$분까지 녹색이라고 했을 때, 그 횡단보도에 정확히 $e$분에 도착했다면 바로 신호가 적색으로 바뀌기 때문에 건너지 않고, $s$분부터 $e-1$분까지는 각 시간에 도착했을 때 바로 건너갈 수 있다.

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

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

두 번째 줄부터 $N+1$ 번째 줄까지 $i+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$를 출력한다. $x$는 항상 음이 아닌 정수이다.