The True FA Student

Interview

Time limit1sMemory limit512 MB

Summary

Find the minimum time to reach zone N, choosing at each crosswalk whether to wait for the green signal or take the footbridge.

Level: Medium4 of 10
Topics: Dynamic programming, Simulation
Solved: No attempts yet

Problem

Sogang University has an FA system that gives an F grade to any student who misses a single course five times. Geunsoo has already missed the Algorithm Design and Analysis course four times, and one more absence will earn him an F. The classroom is not that far away, but the crosswalks on the way slow him down.

Recently the school built a footbridge next to every crosswalk so that students are not late because of traffic signals. With a footbridge, he can cross the road without waiting for the signal, but the route length changes, so it may take longer. Geunsoo wants to reach school as soon as possible by deciding whether to wait for each signal or use the footbridge.

Geunsoo must pass N crosswalks in a row to reach school. For convenience, the N crosswalks divide the road into N+1 zones numbered 0 to N. The crosswalk between zone i-1 and zone i is called the i-th crosswalk. Geunsoo starts in zone 0, and the classroom is in zone N.

For each crosswalk, Geunsoo recorded four values:

$A_i$ : the time to move from zone i-1 to zone i using the crosswalk.
$B_i$ : the time to move from zone i-1 to zone i using the footbridge.
$C_i$ : the number of minutes the i-th signal stays green. It turns red exactly $C_i$ minutes after turning green.
$D_i$ : the number of minutes the i-th signal stays red. It turns green exactly $D_i$ minutes after turning red.

Note that $A_i$ is not the time it takes to cross the i-th crosswalk. It is the time to move between zones using the crosswalk. Crossing a crosswalk takes no time at all. For example, if a signal is green from minute $s$ to minute $e$ , and Geunsoo arrives at exactly minute $e$ , the signal has already turned red, so he cannot cross. If he arrives at any minute from $s$ to $e-1$ , he can cross immediately.

Geunsoo is standing in front of the first crosswalk, and every signal has just turned green at the same moment. Find the minimum time for Geunsoo to reach the classroom.

Input

The first line contains the integer $N$ , the number of crosswalks. $(1\le N \le 100\,000)$

Each of the next $N$ lines contains four integers $A_i$ , $B_i$ , $C_i$ , and $D_i$ , separated by spaces. $(1 \le A_i < B_i \le 100; 1 \le C_i, D_i \le 100)$

Output

Print one line containing $x$ , the minimum number of minutes for Geunsoo to reach the classroom. $x$ is always a non-negative integer.

Examples2

Example 1
Input
```
3
2 3 1 1
1 2 2 4
1 2 2 2
```
Expected output
```
5
```
Example 2
Input
```
3
3 4 1 1
2 100 2 2
1 2 6 6
```
Expected output
```
8
```