配点:400400

問題文

ある祭りでは,NN 個のプログラミングコンテストが開催されます.
何人かでチームを組んで,これらすべてのコンテストを楽しく網羅したいです.

ii 番目のコンテストは,時刻 sis_i から時刻 tit_i まで参加登録が可能で,時刻 tit_i から競技が始まり,時刻 uiu_i に一切が終了します.(1iN)\scriptsize(1 \leq i \leq N)

任意の競プロerは,次のようにして活動を開始することができます:

  • 1iN1 \leq i \leq N なる整数 ii を選び,時刻 tit_iii 番目のコンテストに参加する.

また,任意の競プロerは競プロ中毒であって,活動を開始した後は常にいずれかのコンテストに参加していたいと思っています.

したがって,自身が以前に参加したコンテストが終了するたびに,以下のうちいずれかを行います:

  • そのコンテストの終了時刻を uu として,1iN1 \leq i \leq N かつ siutis_i \leq u \leq t_i を満たす整数 ii を自由に一つ選び,ii 番目のコンテストへの参加登録を行う.
  • 爆発する.

なお,一度参加登録をしたコンテストについては,そのコンテストの一切が終了するまで,そのコンテストの競技に参加する以外の行動はできません.
また,一度爆発した競プロerは,以降いかなる活動をも行うことはできません.

任意の競プロerは十分に強いので,参加したコンテストすべてにおいて賞金を得ることができます.
また,待ち時間が長いとそわそわしてしまいます.

さて,次の条件を満たすようにチームを一つ構成します:

  • 同一の競プロerが,同時に複数のコンテストに参加することがない.
  • 同一のチームに属する複数人の競プロerが,重複して同一のコンテストに参加することがない.
  • チームとして,NN 個すべてのコンテストで賞金を得ることができる.
  • そのような構成のうち,以下のように定められる待ち時間 WW が最小である:
    • チームが nn 人によって構成されるとする.
    • W:=1knwk\displaystyle W := \sum_{1 \leq k \leq n} w_k
    • wkw_k は以下のように定められる:
      • kk 人目のチームメンバーは,順に c1,c2,,cmc_1, c_2, \ldots, c_m 番目の mm 個のコンテストに参加するとする.
      • wk1i<m(tci+1uci)\large\displaystyle w_k \coloneqq \sum_{1 \leq i < m} (t_{c_{i+1}} - u_{c_i})
      • なお m=0m = 0m=1m = 1 のとき,wk=0w_k = 0 であることに留意せよ.

最小のチームの構成人数 nn' と,そのようなチームでの最小の待ち時間 WW' とを求めてください.

制約

  • Φ=1\Phi = 1
  • 1<N501 < N \leq 50
  • 0si<ti<ui<230(1iN)0 \leq s_i < t_i < u_i < 2^{30} \scriptsize \; (1 \leq i \leq N)
  • 入力はすべて整数

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

NN
s1t1u1s_1 \enspace t_1 \enspace u_1
s2t2u2s_2 \enspace t_2 \enspace u_2
\vdots
sNtNuNs_N \enspace t_N \enspace u_N

出力

答えを以下の形式で出力せよ:

nWn' \enspace W'

サンプル

入力例1
1
5
0 2 4
0 1 9
3 6 14
13 22 25
7 18 24
出力例1
2 19

たとえば,11 人の競プロerが 1,3,41, 3, 4 番目のコンテストに参加し,もう 11 人の競プロerが 2,52, 5 番目のコンテストに参加することで,すべてのコンテストを網羅することができます.
また,22 人未満の競プロerでこれを達成することはできません.
これを達成する方法はこの 11 通りのみです.
このときの待ち時間は {(64)+(2214)}+{(189)}=(2+8)+9=19\{ (6 - 4) + (22 - 14) \} + \{ (18 - 9) \} = (2 + 8) + 9 = 19 となります.


入力例2
1
3
1 2 3
4 5 6
6 7 8
出力例2
2 1

11 番目のコンテストに参加した競プロerは,そのコンテストが終了した直後にいずれのコンテストにも参加することができません.したがって爆発します.
残った 22 つのコンテストで賞金を得るためにはもう 11 人の競プロerが必要です.

Submit


Go (1.21)