問題一覧 > 通常問題

No.2713 Just Solitaire

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 64
作問者 : 👑 Nafmo2Nafmo2 / テスター : dyktr_06dyktr_06 sepa38sepa38
0 ProblemId : 10584 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-29 00:46:18

問題文

Nafmoくんはカードゲームをしています.

今,$1$ から $N$ までの番号がついたカードを手札として持っています.番号 $i$ のカードの使用には $A_i$ のお金を消費します.

また, $M$ 種類のボーナスがあり, $i$ 番目のボーナスは 以下の条件を達成することによって $B_i$ のお金を獲得できます.

  • $1 \leq j \leq K_i$ を満たす全ての整数 $j$ について,番号 $C_{i,j}$ のカードが使われている

Nafmo くんは十分にたくさんのお金を持っています.カードを使う組み合わせをうまく決めたとき,Nafmoくんが得る利益の最大値を計算してください.

ここで,利益とは,

「$(ボーナスによって獲得できるお金) - (カードを使うために消費したお金)$」

とし,カードの使用とボーナスの獲得以外でお金は変化しないものとする.

入力

$N \ M$
$A_1 \ \dots \ A_N$
$B_1 \ \dots \ B_M$
$K_1 \ C_{1,1} \ \dots \ C_{1,K_1}$
$\ \vdots$
$K_M \ C_{M,1} \ \dots \ C_{M,K_M}$
  • $1 \leq N, M \leq 100$
  • $1 \leq A_i, B_i \leq 10^9$
  • $1 \leq K_i \leq N$
  • $1 \leq C_{i,1} < C_{i,2} < \dots < C_{i,K_i} \leq N$
  • 入力はすべて整数

出力

Nafmoくんが得ることのできる利益の最大値を出力してください.

サンプル

サンプル1
入力
5 2
10 20 30 40 50
50 120
3 1 2 3
2 4 5
出力
30

$4, 5$ のカードを使ったとき,利益が最大になります.

消費したお金:$40+50 = 90$
獲得したお金:$120$
利益:$120 - 90 = 30$

サンプル2
入力
5 2
10 20 30 40 50
50 120
3 1 2 3
5 1 2 3 4 5
出力
20

全てのカードを使ったとき,利益が最大となります.

消費したお金:$10+20+30+40+50 = 150$
獲得したお金:$50 + 120 = 170$
利益:$170 - 150 = 20$

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。