お知らせ

問題文

新たな旅立ちを迎えるチェリーちゃんは現在, $N$ 個の目標と $M$ 個の行動と $K$ 個の準備を抱えている. これらはそれぞれ, 目標 $1,2, \dots, N$, 行動 $1,2, \dots, M$, 準備 $1,2, \dots, K$ と名付けられている.

チェリーちゃんはこれらの目標, 行動, 準備の中から1つずつ選び, 順に実行する. なお, 2つ以上同時に実行することはできず, 同じ目標, 行動, 準備を複数回実行することはできない.

$i=1,2, \dots, N$ に対して, 目標 $i$ を達成させるためには, それまでに $L_i$ 個の準備 $A_{i,1}, \dots, A_{i,L_i}$ を全て終えなければならないが, この目標を達成させるとチェリーちゃんは経験値として $E_i$ が得られる.

$j=1,2, \dots, M$ に対して, 行動 $j$ をすると, 経験値として $F_j$ を得る.

$k=1,2, \dots, K$ に対して, 準備 $k$ を終わらせるためにはチェリーちゃんは気力として $V_k$ を消費しなければならない. また, 一度着手した準備は途中で終わらせることはできず, 完遂させなければならない.

そして, $p=1,2, \dots, P$ のそれぞれに対して,

• 既に目標 $I_p$ を達成しているならば, その後, 行動 $J_p$ をすることはできない.
• 既に行動 $J_p$ をしているならば, その後, 目標 $I_p$ を達成させることはできない.

では, 達成させる目標とする行動, 終わらせる準備をうまく選び, 適当な順番で実行し, それらを全て実行し終えたあと, (得られた経験値の総和) $-$ (消費した気力の総和) の最大値とその値になるような行動の方法を1つ求めよ.

ここで, チェリーちゃんは最初は十分な気力を持っているので, 準備の途中で気力切れをしないとする.

制約

• $1 \leq N \leq 50$
• $1 \leq M \leq 50$
• $1 \leq K \leq 50$
• $0 \leq P \leq NM$
• $1 \leq E_i \leq 10^9$
• $1 \leq F_j \leq 10^9$
• $1 \leq V_k \leq 10^9$
• $0 \leq L_i \leq K$
• $1 \leq A_{i,1} \lt A_{i,2} \lt \dots \lt A_{i,L_i} \leq K$
• $1 \leq I_p \leq N$
• $1 \leq J_p \leq M$
• $p \neq q$ ならば, $(I_p, J_p) \neq (I_q, J_q)$
• 入力は全て整数である.

入力

$N$ $M$ $K$ $P$
$E_1$ $E_2$ $\dots$ $E_N$
$F_1$ $F_2$ $\dots$ $F_M$
$V_1$ $V_2$ $\dots$ $V_K$
$L_1$ $A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,L_1}$
$L_2$ $A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,L_2}$
$\vdots$
$L_N$ $A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,L_N}$
$I_1$ $J_1$
$I_2$ $J_2$
$\vdots$
$I_P$ $J_P$

出力

以下の形式で出力せよ.

$C$
$T$
${\rm Motion}_1$
${\rm Motion}_2$
$\vdots$
${\rm Motion}_T$

ただし,

• $C$ は (得られた経験値の総和) $-$ (消費した気力) の最大値
• $T$ は実行する目標と行動と準備の数の総和
• ${\rm Motion}_t$ は $t$ 番目に実行する目標や行動, 準備. ただし, 以下のようにして出力せよ.
  • 目標 $i$

    Goal $i$

  • 行動 $j$

    Action $j$

  • 準備 $k$

    Preparation $k$

また, この形式に沿っていない出力に関するジャッジの結果は不定である (WA になるとは限らない).

最後に改行を忘れないこと.

サンプル

3 2 4 2
5 7 8
4 6
1 2 3 4
2 1 2
2 2 4
1 2
3 1
2 2

16
5
Preparation 1
Goal 3
Action 2
Preparation 2
Goal 1

2 2 2 0
1 10
2 20
3 30
0
0

33
4
Goal 1
Action 1
Goal 2
Action 2

2 1 3 1
1 1
1
46 46 46
3 1 2 3
3 1 2 3
1 1

1
1
Action 1