TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3757
  • 問題
  • P3757上课时间
    制限 : 時間制限 : - MS   メモリ制限 : 65536 KB
    審判説明 : 时限1000ms
    問題説明

      由于天气炎热,我校决定放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