004 - 野草さいしゅう

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / x 13 /


TLE
1sec
MLE
64MB
得点
1

問題

YDKは「野草大好きの会」に入っている。野草の採集は彼の日課だ。

YDKは $N$ 種類の野草を採集する。野草の種類ごとに,生えている地点の個数と自宅からの距離が決まっている。

ここで, $i$ 種類目の野草( 1 ≤ $i$ ≤ $N$ )を 野草$i$ と呼ぶことにする。

野草$i$ は $P_i$ 個の地点に生えており,

$j$ 番目の地点 ( 1 ≤ $j$ ≤ $P_i$ ) はYDKの家から di,j の距離がある。

距離 $1$ を移動するのにかかる時間は $1$ である。

彼はまず家から出発して, $P_i$ 個ある地点のうちのどれか1地点(どこでもいい)へ行って野草$i$ を採り,家へ戻る。

この「家 → 採集地 → 家」のサイクルををすべての種類の野草の採集で行う。

YDKは「野菜大嫌いの会」の会合があるので,採集する時間は $T$ 以下で間に合わせなければならない。

そこで,採集地を適切に選んでYDKがタイムリミット $T$ 以内に採集を終わらせることができるかどうかを調べることにした。

なお,今回は採集そのものにかかる時間はないものとし,移動のみに時間がかかるものとする。テレポーテーション能力は失っている。

入出力

入力

N T
P1
d1,1 d1,2 ... d1,P1
P2
d2,1 d2,2 ... d2,P2
  :
PN
dN,1 dN,2 ... dN,PN

1行目に,野草の種類数 $N$ と 採集時間の上限 $T$ が空白区切りで与えられる。

以降, $2N$ 行にわたって各種類の野草が生えている地点についての情報が入力される。

まず野草$i$ が生えている地点の個数 $P_i$ が1行に与えられ,次行に $j$ 番目の地点のYDKの家からの距離 di,j が空白区切りで与えられる。

出力

採集時間が $T$ 以下に収まる採集地の選び方があるならならその最短時間,
ないなら"TLE!"を出力せよ。

改行を忘れないように。

制約

すべての入力について以下の制約を満たす。

  • 入力は全て整数である
  • 1 ≤ $N$ ≤ 1000
  • 1 ≤ $T$ ≤ 1000000
  • 1 ≤ $P_i$ ≤ 1000
  • 1 ≤ di,j ≤ 100000

入出力例

入力例1

2 10
2
3 6
5
2 4 8 4 7

出力例1

10

この例では、野草は2種類あり、タイムリミット $T$ は10である。

野草1は2つの地点に生えており,それぞれ距離が 3 と 6 である。
野草2は5つの地点に生えており,各距離は2, 4, 8, 4, 7 である。

野草1は距離 3 の地点, 野草2は距離 2 の地点で採集すると合計10の時間ががかかり,これが最短である。(往復するので2倍になることに注意)

これは タイムリミット 10 以下なので "TLE!" にはならない。

入力例2

1 5
3
100 3 64

出力例2

TLE!

この場合,最短でも時間が 6 かかってしまい, 5 以下を満たせていないので "TLE!" を出力する。