ダダスは 個のプリズム鉱山を運営しており、 個の採掘モジュールを作ろうとしている。
モジュール には 個の設計候補があり、そのうちちょうど 個を選ぶ。候補 を選ぶと、性能は となり、 時間に 個のプリズムを消費する。すべてのモジュールを必ず作る。消費量は、そのモジュールを使用する鉱山の数に関係なく一度だけ数える。どの鉱山にも使用されないモジュールの消費量も数える。
鉱山 は異なる 個のモジュール を使用する。モジュール で選んだ候補の番号を とすると、この鉱山は 時間に 個のプリズムを採掘する。複数の鉱山が同じモジュールを同時に使用してよい。同じ 個のモジュールを使用する鉱山が複数存在することもあり、各鉱山の採掘量をすべて加算する。
時間当たりの純利益は、すべての鉱山の採掘量の合計から、すべてのモジュールの消費量の合計を引いた値である。この純利益の最大値を求めよ。
入力は以下の形式で与えられる。
時間当たりの純利益の最大値を出力せよ。答えは負になることもある。
最初の行には鉱山の数 とモジュールの数 が与えられる。続く 行には各モジュールの候補数と、各候補の性能および消費量が与えられる。最後の 行には各鉱山が使用する 個のモジュールの番号が与えられる。候補は性能順に並んでいるとは限らない。
| 3 | 55 | 追加の制約はない。 |