配点: 点
ある祭りでは, 個のプログラミングコンテストが開催されます.
何人かでチームを組んで,これらすべてのコンテストを楽しく網羅したいです.
番目のコンテストは,時刻 から時刻 まで参加登録が可能で,時刻 から競技が始まり,時刻 に一切が終了します.
任意の競プロerは,次のようにして活動を開始することができます:
また,任意の競プロerは競プロ中毒であって,活動を開始した後は常にいずれかのコンテストに参加していたいと思っています.
したがって,自身が以前に参加したコンテストが終了するたびに,以下のうちいずれかを行います:
なお,一度参加登録をしたコンテストについては,そのコンテストの一切が終了するまで,そのコンテストの競技に参加する以外の行動はできません.
また,一度爆発した競プロerは,以降いかなる活動をも行うことはできません.
任意の競プロerは十分に強いので,参加したコンテストすべてにおいて賞金を得ることができます.
また,待ち時間が長いとそわそわしてしまいます.
さて,次の条件を満たすようにチームを一つ構成します:
最小のチームの構成人数 と,そのようなチームでの最小の待ち時間 とを求めてください.
各テストケースの入力は,それぞれ以下の形式で与えられる:
答えを以下の形式で出力せよ:
1 5 0 2 4 0 1 9 3 6 14 13 22 25 7 18 24
2 19
たとえば, 人の競プロerが 番目のコンテストに参加し,もう 人の競プロerが 番目のコンテストに参加することで,すべてのコンテストを網羅することができます.
また, 人未満の競プロerでこれを達成することはできません.
これを達成する方法はこの 通りのみです.
このときの待ち時間は となります.
1 3 1 2 3 4 5 6 6 7 8
2 1
番目のコンテストに参加した競プロerは,そのコンテストが終了した直後にいずれのコンテストにも参加することができません.したがって爆発します.
残った つのコンテストで賞金を得るためにはもう 人の競プロerが必要です.