P3757上课时间 | ||
|
问题描述
由于天气炎热,我校决定放n(编号1到n)天的高温假。何老板决定选连续一段时间来搞训练。
信竞班有m名同学,每名同学对上课时间的要求可能不同。比如,i同学希望在Ai到Bi这段时间中选一段来上课,j同学希望在Aj到Bj这段时间中选一段。对此何老板很是头疼。
请你帮何老板选一段时间,能满足所有同学的要求,同时天数尽可能多。
输入格式
第一行,两个整数n和m
接下来m行,每行两个整数A,B表示一个同学希望的上课时间段(A<=B)。
输出格式
一行,两个整数,第一个整数表示上课的天数,第二个表示上课开始的时间
如果无解,输出-1
样例输入
13 3
2 6
4 11
5 11
样例输出
2 5
提示
1<=n<=100000
1<=m<=100000