Migrated from Lutece 916 方老师的分身 III

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

一天的讲座结束后，方老师的分身们聚在了一起。在合并成一个方老师之前。这些分身要求方老师的真身发糖。这些分身要求方老师至少给他们发$888$个糖。这还不够，有的分身要求分比另外某个分身的糖多。问方老师最少分多少糖。

Input

有多组数据。

第一行$2$个整数$N$（$1\leq N\leq 10000$），$M$（$0\leq M\leq 20000$）表示分身数和要求数。

接下来$m$行，每行$2$个整数$x$，$y$。表示$x$要求分的比$y$更多糖果。

Output

一个整数，方老师最少要分多少糖。如过无法完成分糖输出$-1$。

Samples

2 1
1 2
2 2
1 2
2 1

1777
-1

Resources

2014 UESTC Training for Graph Theory