THE BYDOLM@STER(バイドルマスター)とは1rem社より2010/4/1にEXIDNAで発売が予定されている育成シミュレーションゲームである。一応断っておくが、今月初めにネットワーク接続サービスが停止した某アーケードゲームとはたぶん関係が無い。
このゲームはバイドルたちからプロデュースするユニット(編隊)のメンバーを選択し、メンバーたちとのレッスンやコミュニケーションを通じて、彼女(彼)らをバイドルの頂点、トップバイドルに育て上げるゲームである。
各バイドルには能力値としてボーカル、ダンス、ルックスの3つのパラメータを持ち、ユニットの能力値はユニットに属している全てのバイドルのパラメータの合計値となる。ユニットの3つの能力値のうち最大の物がユニットのランクとなる。
ユニットに人数制限は無く、メンバーの人数が1体でも、3体でも、100体でもユニットとして活動できる。もちろん同じバイドルを複数雇うこと出来るが、バイドルを雇うためには費用がかかるのでこれを考慮に入れなければならない。
プロデューサーであるあなたは最高のユニットを作るためにプログラムを書いて計算することにした。
入力は複数のテストケースからなる。
各テストケースの1行目にはバイドルの数Nと使用可能な費用Mが与えられる。(1<=N,M<=300)
次の2*N行には各バイドルに関しての情報が書かれている。
バイドルの情報の1行目にはバイドルの名前。バイドルの名前はアルファベットと空白から成り、30文字を以下である。また同一名のバイドルは存在しない。
2行目には整数C、V、D、Lが与えられる。Cはそのバイドルを1体雇用するコスト、Vはボーカル、Dはダンス、Lはルックスの能力値を表す。(1<=C,V,D,L<=300)
入力はEOFで終わる。
与えられた費用の中で作れるユニットのランクの最大値を答えよ。
ユニットが作れない場合は0を出力せよ。
3 10 Dobkeradops 7 5 23 10 PataPata 1 1 2 1 dop 5 3 11 14 2 300 Bydo System Alpha 7 11 4 7 Green Inferno 300 300 300 300
29 462