011 - モンスター甲子園
時間制限 3 秒 / メモリ制限 256 MB / 得点 10 / x 0 /
問題
あなたは近日開かれるモンスター甲子園に、育てているモンスターを出場させようとしています。モンスター甲子園では相手モンスターが何体か出現し、それらのモンスターと一対一で順番に試合を行います。勝利してもしなくても、次の試合に進めます。試合では、対戦するモンスター同士が持っている、すばやさ、ちからづよさ、かしこさ、の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