011 - モンスター甲子園

時間制限 3 秒 / メモリ制限 256 MB / 得点 10 / x 0 /


TLE
3sec
MLE
256MB
得点
10

問題

あなたは近日開かれるモンスター甲子園に、育てているモンスターを出場させようとしています。モンスター甲子園では相手モンスターが何体か出現し、それらのモンスターと一対一で順番に試合を行います。勝利してもしなくても、次の試合に進めます。試合では、対戦するモンスター同士が持っている、すばやさ、ちからづよさ、かしこさ、の3つの数値を比較し、そのうち2つ以上の数値の大きさが上回っているモンスターが勝利となります。
相手モンスターとの対戦を有利に進めるために、あなたのモンスターの数値を調整することができます。金貨1枚を支払うと、3つの数値のうちひとつだけ、大きさを1増やしてもらえます。その代わりに他の2つの数値のうちどちらかの大きさを1減らさなければなりません。数値はいくらでも大きくできますが、負にならないように増減させる必要があります。数値の調整は各試合の前に行うことができ、そのとき金貨を何枚使ってもかまいません。金貨があるかぎり数値の調整が可能です。また、増減した数値は以降の試合に引き継がれます。
あなたは、相手モンスターの情報を入手し、自分のモンスターをどのように戦わせるかを考えているところです。
あなたのモンスターの各数値と、試合前に対戦するモンスターの各数値、対戦する順番、使うことのできる金貨の枚数が与えられる。このとき、あなたのモンスターが勝利する試合の最大数を計算するプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $C$
$a$ $s$ $w$
$a_1$ $s_1$ $w_1$
$\vdots$
$a_N$ $s_N$ $w_N$

1行目に試合の数$N$($1 \leq N \leq 50$)と使うことのできる金貨の枚数$C$($1 \leq C \leq 5000$)が与えられる。続く1行にあなたのモンスターのすばやさ($0 \leq a \leq 100$)、ちからづよさ($0 \leq s \leq 100$)、かしこさ($0 \leq w \leq 100$)が与えられる。続く$N$行に$i$番目に対戦するモンスターのすばやさ($0 \leq a_i \leq 100$)、ちからづよさ($0 \leq s_i \leq 100$)、かしこさ($0 \leq w_i \leq 100$)が与えられる。

出力

あなたのモンスターが勝利する試合の最大数を出力する。

入出力例

入力例1

2 22
10 30 50
30 100 10
20 50 50

出力例1

2

入力例2

3 30
30 30 0
70 25 20
25 30 60
20 25 90

出力例2

2