Meeting Time

Time limit1sMemory limit256 MB

Summary

Find the smallest total travel time that both cows can achieve on separate downhill paths from field 1 to field N.

Level: Medium5 of 10
Topics: Dynamic programming, Graph
Solved: No attempts yet

Problem

Bessie and Elsie travel downhill from field 1 to field $N$ on a DAG. Each path has Bessie time $C$ and Elsie time $D$ . Find the minimum time when both can arrive at field $N$ together, or IMPOSSIBLE.

Input

$N$ , $M$ , then $M$ lines with $A$ , $B$ , $C$ , $D$ ( $A < B$ ).

Output

Minimum equal arrival time, or IMPOSSIBLE.

Examples3

Example 1
Input
```
3 3
1 3 1 2
1 2 1 2
2 3 1 2
```
Expected output
```
2
```
Example 2
Input
```
2 1
1 2 5 5
```
Expected output
```
5
```
Example 3
Input
```
2 0
```
Expected output
```
IMPOSSIBLE
```