Elevator

Time Limit: 8 sec / Memory Limit: 64 MB

E: エレベータ

あなたの友人は，キリンのマークの引越業者でアルバイトをしている． 彼の仕事は，建物から荷物を運び出すことである．

今回，彼はあるn階建てのビルからいくつかの荷物を運び出すことになった． 幸い，このビルにはエレベータが1つ備え付けられているため， エレベータで荷物を運び出すことにした．

運び出すべき荷物は，各階に複数個あり，荷物毎に重さが異なる． エレベータには，重量制限が設定されており，重さWを超える荷物を載せることはできない． エレベータは十分に広く，重量制限を満たすならば，どれだけ多くの荷物でも載せることができる．

エレベータは停止した階で荷物の搬入と搬出を行うことができる． ベテランアルバイターである彼は，エレベータに乗らずに，階段で移動する． エレベータに荷物を積み込んだ後，階段で次のエレベータの停止フロアに先回りし，荷物の搬入と搬出を行うのだ． ベテランアルバイターの彼は，荷物の搬入と搬出を非常に高速に行うことができるので，各フロアでのエレベータの停止時間は，無視することができる． よって，全ての荷物を1階に移動させるのに必要な時間は，エレベータの移動距離から容易に算出できる．

彼は，荷物をできるだけ早く1階に移動させたい． 彼はベテランアルバイターではあるが，どのような手順で各階での荷物の出し入れを行えばよいのか分からない． そこで，彼は，友人であるあなたに助けを求めてきた．

あなたの仕事は，彼が全ての荷物を1階に移動させるために必要なエレベータの最小の移動距離を求めることである．

Input

入力は以下の形式で与えられる．

n m W
1階の荷物の情報
...
i 階の荷物の情報
...
n 階の荷物の情報

i階の荷物の情報は，以下の形式で与えられる．(1 <= i <= n)

ki w1 w2, ..., wj, ..., wki

入力の形式の各変数の意味は次の通りである．

• n はフロア数(1 <= n <= 10000)
• m はエレベータの初期位置(1 <= m <= n)
• W はエレベータの重量制限(1 <= W <= 10000)
• k_i は荷物の数(0 <= k_i <= 15, 1 <= k₁ + k₂ + ... + k_n <= 15)
• w_j は荷物 j の重さ(1 <= w_j <= W)

Output

最小の移動距離を1行で出力せよ．

Sample Input 1

3 3 2
1 1
2 1 1
3 1 1 1

Sample Output 1

8

Sample Input 2

3 3 10
0
2 4 5
3 3 3 5

Sample Output 2

6

Sample Input 3

3 3 100
5 3 4 5 6 7
0
0

Sample Output 3

0