D - 買い物上手 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんはゲームにはまっています。このゲームではいくつかのアイテムの組み合わせを満たすと経験値が得られます。アイテムの値段と、アイテムの組み合わせによって得られる経験値の一覧が与えられるので、買うアイテムを上手く選んで「得られた経験値 ÷ 使ったお金」を最大にしてください。ただし、アイテムは 1 種類以上買うこととし、1 種類につき 1 個だけ持っておけば経験値が得られます。

入力

入力は以下の形式で標準入力から与えられる。

N M
S1 S2 ... SN
T1 T2 ... TM
K1 A1,1 A1,2 ... A1,K1
K2 A2,1 A2,2 ... A2,K2
:
KN AN,1 AN,2 ... AN,KN
  • 1 行目には、経験値をもらえる組み合わせの数 N (1≦N≦100) とアイテムの種類数 M (1≦M≦100) がスペース区切りで与えられる。
  • 2 行目には、もらえる経験値の大きさ Si (1≦Si≦100) が与えられる。
  • 3 行目には、アイテムの値段 Ti (1≦Ti≦100) が与えられる。
  • 4 行目からの N 行では、経験値をもらえる組み合わせに含まれるアイテムの種類数 Ki (1≦Ki≦10) と、アイテムの番号を表す Ki 個の整数 Ai,j (1≦Ai,j≦M, Ai,j<Ai,j+1) がスペース区切りで 1 行ずつ与えられる。

出力

「得られた経験値 ÷ 使ったお金」の最大値を出力せよ。絶対誤差、または、相対誤差が 10−4 以下であれば許容される。出力の末尾には改行をつけること。

部分点

この問題には 2 つのデータセットがあり、データセット毎に部分点が設定されている。

  • N≦10 を満たすデータセット 1 に正解した場合は 50 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、上記のデータセットとは別に 50 点が与えられる。

入力例1

3 4
4 3 2
4 2 1 10
2 1 2
2 1 3
3 2 3 4

出力例1

1

アイテム 1 、アイテム 2 、アイテム 3 を買うと、使ったお金は 7で、経験値が 4+3=7 得られます。

入力例2

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

出力例2

2.8