题目描述

两人同时从1号牧场出发，分别选择路径前往 $N$ 号牧场。只能从编号小的牧场走向编号大的牧场，不能在途中等待。每条道路分别给出两人的通行时间。求她们能同时到达终点的最早时刻。

输入格式

第一行 $N,M$。接下来 $M$ 行，每行 $A,B,C,D$，表示道路从 $A$ 到 $B$，两人的用时分别是 $C,D$。

输出格式

输出最早共同到达时刻；不存在则输出 IMPOSSIBLE。

样例

3 3
1 3 1 2
1 2 1 2
2 3 1 2

2

数据范围

对于20%的数据，$N\le5$；对于60%的数据，$M\le90$；对于100%的数据，$1\le N\le16$，$0\le M\le N(N-1)/2$，$1\le A<B\le N$，$1\le C,D\le1000$。无重边。