No.472 平均順位

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-5}$ 以下
タグ : / 解いたユーザー数 66
作問者 : roiti46roiti46 / テスター : ぴろずぴろず

1 ProblemId : 734 / 出題時の順位表

Note

この問題はAdvent Calendar Contest Advent Calendar 2016の22日目の問題として作られました。

C++, PyPy2でACできることは確認していますがPythonではTLEします
PyPy2で提出したwriter解は1200msほどでACしています

問題文

yukiさんは「するめふぉーしーず」というクイズを解くコンテストが好きで、毎回欠かさず出ています。
毎回3問のクイズが出され、解いた問題数によって順位が決まります(提出のはやさは関係しません)。
つまり、3問解ければ必ず1位タイになれます。

ある日、運営のデータベースが消失してしまい、各コンテストで n (0 ≤ n ≤ 3) 問解けた場合の順位と、
あるユーザーが今までコンテスト中に解いた問題数の合計しか残りませんでした。

yukiさんは自分の平均順位を知りたいと思ったのですがそれも叶いません。
とりあえず、とりうる平均順位の最小値を自分の平均順位にすることにしました。

忙しいyukiさんの代わりにyukiさんの平均順位の最小値を求めてください。

なお、各コンテストにおいて解いた問題数が0問、1問、2問、3問のユーザーはそれぞれ1人以上存在するとします。

入力

$N$ $P$
$a_0$ $b_0$ $c_0$
$a_1$ $b_1$ $c_1$
.
.
.
$a_{N-1}$ $b_{N-1}$ $c_{N-1}$

$N$: コンテストの数
$P$: yukiさんがコンテスト中に解いた問題数
$a_k$ $b_k$ $c_k$: $k$番目のコンテストで解いた問題数が0問、1問、2問だったときの順位(3問の場合は常に1位です)

すべての入力は以下の制約を満たします。
$1 \leq N \leq 5000$
$0 \leq P \leq 3N$
$100000 \geq a_k \gt b_k \gt c_k \gt 1$

出力

yukiさんの平均順位の最小値を出力してください。
出力に相対誤差または絶対誤差が$10^{-5}$以下あってもかまいません。

サンプル

サンプル1
入力
2 2
100 50 10
999 990 4
出力
52.0

1つ目のコンテストで0問解いて100位、
2つ目のコンテストで2問解いて4位をとったとした場合、
平均順位52位で最小になります。

サンプル2
入力
2 2
200 50 4
115 70 5
出力
59.5

1つ目のコンテストで2問解いて4位、
2つ目のコンテストで0問解いて115位をとったとした場合
平均順位59.5位で最小になります。

サンプル3
入力
2 0
332 33 2
114 51 4
出力
223.0

yukiさんはクイズが得意ではないらしい。

サンプル4
入力
3 9
123 45 6
789 12 3
456 78 9
出力
1.0

yukiさんはクイズのプロらしい。

提出ページヘ