ICPC で良い成績を収めるには修行が欠かせない．うさぎは ICPC で勝ちたいので，今日も修行をすることにした．
今日の修行は，街を駆け回り交易を行うことで，商売の力を手にしようというものである．
今後の修行のためにも，できるだけ多くの資金を稼ぎたい．
この世界は，東西南北方向の道路が等間隔に並んでいて，碁盤状になっている．唯一存在する市場の位置を (0, 0)，街には x 座標，y 座標が定まっている (座標が整数値の点が交差点に対応する)．うさぎは道路に沿ってのみ移動することができ，隣接する交差点間を移動するのに 1 分を要する．いくつかの交差点には街がある．交易では，街で商品を買い，市場にて販売することによって価格の差の分の利益を得る．
うさぎの初期資金は十分にあり，お金が足りないから商品が購入できない，といったことはない．だが，それぞれの商品には重さがあり，うさぎは重さの合計が W までの商品しか同時に持ち運ぶことができない．よって，街に商品を仕入れに行ったり市場に戻ったりを繰り返すことになる．場合によっては，複数の街で商品を購入してから市場に戻ることになるかもしれない．
街での商品の購入や，市場での商品の販売は一瞬で行えるものとする．また，街にある商品が品切れになってしまうことは有り得ず，無限に購入することが可能である．
うさぎは，今回売買を行おうとしている各商品の名前，1 個あたりの重さおよび販売価格と，各街の x 座標，y 座標および販売商品の名前と価格を，データにまとめた．うさぎは今，市場がある (0, 0) の位置にいる．プログラムを使って，制限時間 T 分の間にどれだけ稼ぐことが可能か調べたい．
N M W T S1 V1 P1 ... SM VM PM L1 X1 Y1 R1,1 Q1,1 ... R1,L1 Q1,L1 ... LN XN YN RN,1 QN,1 ... RN,LN QN,LN
N は街の数，M は商品の種類数である．Si, Vi, Pi (1 ≤ i ≤ M) はそれぞれ，i 番目の商品の名前，1 個あたりの重さ，1 個あたりの販売価格である． 街は 1 以上 N 以下の整数で表される．Lj, Xj, Yj (1 ≤ j ≤ N) はそれぞれ，街 j で売られている商品の種類数，街 j の x 座標，y 座標である．Rj,k, Qj,k (1 ≤ j ≤ N，1 ≤ k ≤ Lj) はそれぞれ，街 j で売られている k 番目の商品の名前，価格である．
1 ≤ N ≤ 7，1 ≤ M ≤ 7，1 ≤ W ≤ 10,000，1 ≤ T ≤ 10,000，1 ≤ Vi ≤ W，1 ≤ Pi ≤ 10,000，1 ≤ Lj ≤ M，-10,000 ≤ Xj ≤ 10,000，-10,000 ≤ Yj ≤ 10,000，1 ≤ Qj, k ≤ 10,000 を満たす．商品の名前はアルファベット小文字からなる長さが 1 以上 7 以下の文字列である．その他の値はすべて整数である．Si はすべて異なる．(Xj, Yj) として同一の組は複数回現れず，(Xj, Yj) = (0, 0) となることはない． 各 j に対して Rj, k はすべて異なり，各 Rj，k はいずれかの Si に一致する．
うさぎが得られる最大の利益を 1 行に出力せよ．
2 2 100 20 alfalfa 10 10 carrot 5 10 1 1 6 carrot 4 1 -3 0 alfalfa 5
170
2 3 100 20 vim 10 10 emacs 5 10 vstudio 65 100 2 1 6 emacs 4 vstudio 13 3 -3 0 vim 5 emacs 9 vstudio 62
183